1 条题解
-
0
求树的直径,两遍dfs即可
//蒟蒻的代码 #include<iostream> #include <vector> using namespace std; const int N = 10000 + 10; int n, c, d[N]; vector<int> e[N];//用vector存储树 void dfs(int u, int fa) { for (int v : e[u]) { if (v == fa) continue; d[v] = d[u] + 1; if (d[v] > d[c]) c = v; dfs(v, u); } } int main() { scanf("%d", &n); //输入 for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; e[x].push_back(y); e[y].push_back(x); } //两遍dfs dfs(1, 0); d[c] = 0; dfs(c, 0); cout << d[c] << endl; return 0; }
- 1
信息
- ID
- 406
- 时间
- 500ms
- 内存
- 1536MiB
- 难度
- 9
- 标签
- 递交数
- 18
- 已通过
- 4
- 上传者