1021 Deepest Root（dfs，图的联通子集个数，树的深度）

àì夳堔傛蜴生んèń 2024-04-08 09:45 61阅读 0赞

## 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 N N ( ≤ 1 0 4 ≤10^4 ≤104) which is the number of nodes, and hence the nodes are numbered from  1 1 1 to  N N N. Then  N − 1 N−1 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 N ，和  N − 1 N-1 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 在线画图工具 ####

首先，安利一个在线[画图工具][Link 1]

例如：

Sample Output 1:
    5
    1 2
    1 3
    1 4
    2 5

![在这里插入图片描述][cda42eae155d4f7baa1daa3cc3cc5be6.png]

Sample Input 2:
    5
    1 3
    1 4
    2 5
    3 4

![在这里插入图片描述][666544b3c9814cbd8c7f65f6e624a179.png]

### 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;
    }

![在这里插入图片描述][6ddcc9fb67464cd3841da57fc65f98ee.png]

[1013 Battle Over Cities]: https://blog.csdn.net/qq_46371399/article/details/126367701
[Link 1]: https://csacademy.com/app/graph_editor/
[cda42eae155d4f7baa1daa3cc3cc5be6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/4d7f19435fdb4ef78a75a9343210a0d6.png
[666544b3c9814cbd8c7f65f6e624a179.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/684dd69f314c4612b71b00860135e036.png
[6ddcc9fb67464cd3841da57fc65f98ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/be6e424882834f44ab5322dfc89dead9.png