暴力搜索...用dfs判断连通分量个数。如果不是1，连通分量个数，如果是1，输出根节点序号（使得树高最大的根节点）。
有人用两次dfs，说什么这两次搜索的末端节点的并集就是答案，这背后是不是有什么数学原理？不太理解。我直接暴力搜索了，逐个节点进行dfs,过程中记录节点高度。好在没有超时。这道题给了2000ms的时间，一般的题都是400ms，出题者这不就是默认了暴力搜索也是正解吗...
ps:我大概能懂那个思路了，无论从哪个节点开始dfs，高度最高的节点一定是红色节点，可能是左边可能是右边。从这一次dfs搜索出来的高度最高的任一节点再次进行dfs，可以得到另一边的红色节点，这些红色节点的并集，就是题目要求的根节点。
1 #include <iostream> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 vector<int> V(10010); 6 vector<vector<int> > E(10010); 7 vector<int> visited(10010,0); 8 int Max=0; 9 void dfs(int v,int height){ 10 visited[v]=1; 11 if(height>V[v])//每个节点存的是它的最大高度 12 V[v]=height; 13 if(height>Max)//Max存的是最大高度 14 Max=height; 15 for(int i=0;i<E[v].size();i++){ 16 if(visited[E[v][i]]==0) 17 dfs(E[v][i],height+1); 18 } 19 } 20 int main() 21 { 22 int N; 23 scanf("%d",&N); 24 int c1,c2; 25 for(int i=1;i<N;i++){ 26 scanf("%d%d",&c1,&c2); 27 E[c1].push_back(c2); 28 E[c2].push_back(c1); 29 } 30 int cnt=0; 31 for(int i=1;i<=N;i++){ 32 if(visited[i]==0) 33 {dfs(i,1); 34 cnt++; 35 } 36 } 37 if(cnt!=1) 38 printf("Error: %d components",cnt); 39 else 40 { for(int i=1;i<=N;i++) 41 { fill(visited.begin(),visited.begin()+N+1,0); 42 dfs(i,1); 43 } 44 for(int i=1;i<=N;i++) { 45 if(V[i]==Max) 46 printf("%d\n",i); 47 } 48 } 49 return 0; 50 }
原文：https://www.cnblogs.com/wsshub/p/12535474.html