1021 Deepest Root #
0、题目 #
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$ ($≤10^4$) 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
1、大致题意 #
给出无向图的顶点个数 $N$ ，和 $N-1$ 条边，判断这个无向图可不可以转化成树。
- 如果可以，给出所有具有最大深度树的树根+ 如果不行，输出连通子集个数
2、基本思路 #
2.1 无向图转化为树的条件 #
首先一个问题，怎样可以判断一个无向图可以转化为树？
图必须是无回路的连通图+ 当该图为有n-1条边的连通图，也为树
这边可以思考一下为什么满足以上两个条件只一就行。应该画个图就行。
2.1 判断图连通分量的个数 #
有两种方法 ——dfs 和 并查集。
在前面的
1013 Battle Over Cities 使用过使用并查集查找连通子集的个数，这边就使用 dfs 。
vis[] 记录访问历史， 访问过该结点就跳过，没有访问过就dfs(i)，同时连通分量数+1，即：如果图是连通的，dfs一次就可以访问到所有结点。+ 如果该图为树，让每个结点都做一次根，deep[]记录每个结点为根时的树的深度，对每个结点dfs_deep()，用tmp记录当前的深度，并与max_deep比较，如果有更大的就更新vector<int>ans。
3、解题过程 #
3.1 在线画图工具 #
首先，安利一个在线 画图工具
例如：
Sample Output 1:
5
1 2
1 3
1 4
2 5
Sample Input 2:
5
1 3
1 4
2 5
3 4
3.2 AC代码 #
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=10040;
const int maxm=100050;
struct Edge {
int to,next;
} edge[maxm];
int n,head[maxn],vis[maxn],num_edge;
int num_components,max_deep,tmp;
vector<int>ans;
void addedge(int from,int to) { //头插法插入结点
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
head[from]=num_edge;
}
void dfs(int x) {
int k=head[x];
while(k!=0) {
if(vis[edge[k].to]==1) {
k=edge[k].next;
continue;
}
vis[edge[k].to]=1;
dfs(edge[k].to);
k=edge[k].next;
}
}
void dfs_deep(int x,int deep) { //dfs查找最大深度
if(!vis[x]) {
vis[x]=1;
int k=head[x];
while(k!=0) {
if(vis[edge[k].to]==1) {
k=edge[k].next;
continue;
}
dfs_deep(edge[k].to,deep+1);
tmp=max(deep+1,tmp);
k=edge[k].next;
}
}
}
int main() {
cin>>n;
int a,b;
memset(edge,0,sizeof(edge));
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
for(int i=0; i<n-1; i++) {
cin>>a>>b;
addedge(a,b);
addedge(b,a);
}
num_components=0;
for(int i=1; i<=n; i++) {
if(vis[i]==0) {
dfs(i);
num_components++;
}
}
if(num_components!=1) { //图不能转化为树
cout<<"Error: "<<num_components<<" components";
} else {
max_deep=-1;
for(int i=1; i<=n; i++) {
memset(vis,0,sizeof(vis));
tmp=0;
dfs_deep(i,0);
if(tmp>max_deep) { //当前深度大于最大深度
ans.clear();
ans.push_back(i);
max_deep=tmp;
} else if(tmp==max_deep) { //当前深度等于最大深度
ans.push_back(i);
max_deep=tmp;
}
}
cout<<ans[0];
for(int i=1; i<ans.size(); i++) {
cout<<"\n"<<ans[i];
}
}
return 0;
}
