首页 > 代码库 > 树的高度
树的高度
现在有一颗合法的二叉树，树的节点都是用数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度。
分析：输入n个顶点，n-1条边，如果是完全合法的输入，那就简单的有向图，找入度为0的节点，然后广搜或者深搜（深搜代码简单），得到最大的深度就是树的高度。
但是：只过了70%的测试用例，我实在想不出来还有什么情况，1000的数据范围肯定不会超时，我怀疑是否存在非法输入，比如一个节点有超过2个节点的儿子。如果你知道，希望告知一下，谢谢！
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e3 + 10;14 vector<int> e[maxn];15 int n;16 int res;17 void dfs(int u, int d) {18 res = max(res, d);19 for (auto x : e[u]) {20 dfs(x, d + 1);21 }22 }23 int du[maxn];24 void solve() {25 cin >> n;26 int x, y;27 for (int i = 0; i < n - 1; i++) {28 cin >> x >> y;29 e[x].push_back(y);30 du[y]++;31 }32 for (int i = 0; i < n; i++) {33 if(du[i] == 0)34 dfs(i, 1);35 }36 cout << res << endl;37 38 }39 int main() {40 freopen("test.in", "r", stdin);41 //freopen("test.out", "w", stdout);42 solve();43 return 0;44 }
树的高度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。