A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N−1 lines follow, each describes an edge by given the two adjacent nodes' numbers.
Output Specification:
For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print Error: K components
where K
is the number of connected components in the graph.
Sample Input 1:
5
1 2
1 3
1 4
2 5
Sample Output 1:
3
4
5
Sample Input 2:
5
1 3
1 4
2 5
3 4
Sample Output 2:
Error: 2 components
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define MAXN 10005 //卡4088我也是醉了 #define INF 9999999 int G[MAXN][MAXN]; int vis[MAXN] = {0}; int n; int maxdepth = 0; vector<vector<int>> mp; set<int> st; vector<int> vec; void dfs(int x,int depth){ if(depth > maxdepth){vec.clear();vec.push_back(x);maxdepth = depth;} //这个写法在图中很常见,用vec来保存最长的路径 else if(depth == maxdepth){vec.push_back(x);} vis[x] = 1; for(int i=0;i < mp[x].size();i++){ if(!vis[mp[x][i]]){ dfs(mp[x][i],depth+1); } } } int main(){ cin >> n; mp.resize(n+1); //要先开辟空间,不然下面赋值不了 for(int i=1;i <= n-1;i++){ int x1,y1; cin >> x1 >> y1; mp[x1].push_back(y1); mp[y1].push_back(x1); } int cnt=0; for(int i=1;i <= n;i++){ if(vis[i] == 0){ dfs(i,1); cnt++; } } if(cnt!=1){ printf("Error: %d components",cnt); return 0; } int x = (vec.size())?vec[0]:0; fill(vis,vis+n+1,0); //1-n这里一开始写错了 for(int i=0;i < vec.size();i++){ st.insert(vec[i]); } vec.clear();maxdepth = 0; dfs(x,1); for(int i=0;i < vec.size();i++){ st.insert(vec[i]); } for(auto it=st.begin();it!=st.end();it++){ cout << *it << endl; } return 0; }
卡内存,要用vector不用二维数组
先dfs一次找到离1(随便一个节点)最远的节点保存再vec中
然后再从对任意一个vec中的节点dfs找到相对最远的节点,然后对两次的dfs取交集
尼玛好难啊透