第四天PAT

第四天PAT"/>

第四天PAT

A1021

Description:

给出一个图，求可以得到最大深度树的根节点。

详细推导证明过程见“《算法笔记上级实战训练》P344，证明过程如下“，实际遇到这样难以证明正确性的题，还是很难受的，不专注导致一道题写了两个多小时没写出来，反思一下，明天加油。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 1e4+5;
vector<int>adj[maxn];   //邻接表
set<int>ans;    //答案集合
int fa[maxn];   //并查集father数组
int n, cnt;     //结点数n，总集合数cnt
void init(){    //初始化father数组，最初集合数为nfor(int i = 1; i <= n; i++)fa[i] = i;cnt = n;
}
int get(int a){ //路径压缩get fatherif(a == fa[a])return a;return fa[a] = get(fa[a]);
}
void mer(int a, int b){ //合并a = get(a);b = get(b);if(a != b){fa[a] = b;cnt--;}
}
int maxlevel = 0;
vector<int> depest;
void dfs(int n, int level, int pre){    //深搜if(level > maxlevel){   //当前深度大于最大深度maxlevel = level;   //更新最大深度depest.clear();     //原先最大深度记录作废depest.push_back(n);    //记录当前最大深度节点}else if(level == maxlevel){    //和最大深度同一深度depest.push_back(n);    //记录}if(adj[n].size() == 0)  //叶子节点无条件返回return ;for(vector<int>::iterator it = adj[n].begin();it != adj[n].end(); it++){  //对于当前节点的所有邻接边if(*it != pre){     //如果和来路不同，则深搜之dfs(*it, level+1, n);}}
}int main()
{
#ifdef ONLINE_JUDGE
#elsefreopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGEscanf("%d", &n);init();int a, b;for(int i = 0; i < n-1; i++){scanf("%d%d", &a, &b);mer(a, b);adj[a].push_back(b);    //双向存储adj[b].push_back(a);}if(cnt != 1){   //集合数不为一个集合，非树结构printf("Error: %d components\n", cnt);return 0;}dfs(1, 1, -1);  //任意节点首次深搜for(int i = 0; i < depest.size(); i++){ans.insert(depest[i]);  //将最深节点加入结果集}set<int>::iterator it = ans.begin();dfs(*it, 1, -1);    //对于结果集中任意节点(深度相同)深搜，获得另一侧的根节点for(int i = 0; i < depest.size(); i++){ans.insert(depest[i]);}for(set<int>::iterator it = ans.begin(); it != ans.end(); it++){printf("%d\n", *it);}return 0;
}