题目
acyclic 无环的
解决
思路
思路一（我的思路）：
由于结点的最大数量为10000，所以使用邻接表存储图题目要求找最深的树的根结点编号，所以可以将每个结点作为起点，利用DFS或者BFS计算树的深度， 记录在height[N]数组中，然后找深度等于最大深度的根的编号输出即可。存在不能构成一棵树的情况，即图不是连通图，此时要计算连通子图的数量，可以利用DFS或者DSU进行计算，由于这里前面已经写了DFS，所以继续使用DFS计算就可以了。注意：
在计算连通子图的数量之前，以及循环起点之前，都需要对vis[N]数组进行初始化 思路二（算法笔记）：
利用并查集计算连通子图的数量，如果连通子图的数量>1，就说明图不连通，反之连通，进入下面的逻辑题目保证只有N-1条边，说明一定是一棵树，然后就是选择合适的根结点，使得树的高度最大。具体做法：先任意选择一个结点，从该结点开始遍历整棵树，获取能达到的最深的顶点(记为结点集合A)；然后从集合A中任意一个结点出发遍历整棵树，获取能达到的最深的顶点(记为结点集合B)。集合A和集合B的并集就是所求的结果（具体证明看书P344~345） 思路三（柳神）：
整体思路与思路二一致直接用DFS求了连通子图的数量用set代替了vector，此时不需要进行排序和去重
实现
Code1
#include<cstdio>
#include<vector>
using namespace std;
const int N = 10010;
vector<int> Adj[N];
bool vis[N];
int height[N] = {0};
int n;
void init(){
for(int i=1; i<=n; i++){
vis[i] = false;
}
}
void DFS(int& h, int u, int depth){
if(depth > h){
h = depth;
}
vis[u] = true;
for(int i=0; i<Adj[u].size(); i++){
int v = Adj[u][i];
if(vis[v] == false){
DFS(h, v, depth+1);
}
}
}
void DFSTravel(){
for(int i=1; i<=n; i++){
init();
DFS(height[i], i, 1);
}
}
int countComponent(){
init();
int cnt = 0;
for(int i=1; i<=n; i++){
if(vis[i] == false){
cnt++;
DFS(height[0], i, 1);
}
}
return cnt;
}
int main(){
scanf("%d", &n);
int u, v;
for(int i=0; i<n-1; i++){
scanf("%d%d", &u, &v);
Adj[u].push_back(v);
Adj[v].push_back(u);
}
int numComponent = countComponent();
if(numComponent > 1){
printf("Error: %d components\n", numComponent);
}else{
DFSTravel();
int maxHeight = -1;
for(int i=1; i<=n; i++){
if(height[i] > maxHeight){
maxHeight = height[i];
}
}
int ans = 0;
for(int i=1; i<=n; i++){
if(height[i] == maxHeight){
printf("%d\n", i);
}
}
}
return 0;
}
Code2（算法笔记）
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 100010;
vector<int> G[N];
bool isRoot[N];
int father[N];
int findFather(int x){
int a = x;
while(x != father[x]){
x = father[x];
}
while(a != father[a]){
int z = a;
a = father[a];
father[z] = x;
}
return x;
}
void Union(int a, int b){
int faA = findFather(a);
int faB = findFather(b);
if(faA != faB){
father[faA] = faB;
}
}
void init(int n){ //并查集初始化
for(int i=1; i<=n; i++){
father[i] = i;
}
}
int calBlock(int n){
int Block = 0;
for(int i=1; i<=n; i++){
isRoot[findFather[i]] = true;
}
for(int i=1; i<=n; i++){
Block += isRoot[i];
}
return Block;
}
int maxH = 0;
vector<int> temp, Ans; //temp:临时存放DFS的最远结果，Ans:答案
//u：当前访问结点编号
//Height：当前树高
//pre：u的父结点
void DFS(int u, int Height, int pre){
if(Height > maxH){
temp.clear();
temp.push_back(u);
maxH = Height;
}else if(Height == maxH){
temp.push_back(u);
}
for(int i=0; i<G[u].size(); i++){
//由于邻接表中存放无向图，因此需要跳过回去的边
if(G[u][i] == pre) continue;
DFS(G[u][i], Height+1, u);
}
}
int main(){
int a, b, n;
scanf("%d", &n);
init(n);
for(int i=1; i<n; i++){
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
Union(a, b);
}
int Block = calBlock(n);
if(Block != 1){
printf("Error: %d components\n", Block);
}else{
DFS(1, 1, -1); //从1号结点开始DFS
Ans = temp;
DFS(Ans[0], 1, -1); //从任意一个根结点开始遍历
for(int i=0; i<temp.size(); i++){
Ans.push_back(temp[i]);
}
sort(Ans.begin(), Ans.end()); //按编号从小到大排序
printf("%d\n", Ans[0])
for(int i=1; i<Ans.size(); i++){
if(Ans[i] != Ans[i-1]){ //重复编号不输出
printf("%d\n", Ans[i]);
}
}
}
}
Code3（柳神）
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int n, maxheight = 0;
vector<vector<int>> v;
bool visit[10010];
set<int> s;
vector<int> temp;
void dfs(int node, int height) {
if(height > maxheight) {
temp.clear();
temp.push_back(node);
maxheight = height;
} else if(height == maxheight){
temp.push_back(node);
}
visit[node] = true;
for(int i = 0; i < v[node].size(); i++) {
if(visit[v[node][i]] == false)
dfs(v[node][i], height + 1);
}
}
int main() {
scanf("%d", &n);
v.resize(n + 1);
int a, b, cnt = 0, s1 = 0;
for(int i = 0; i < n - 1; i++) {
scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
for(int i = 1; i <= n; i++) {
if(visit[i] == false) {
dfs(i, 1);
if(i == 1) {
if (temp.size() != 0) s1 = temp[0];
for(int j = 0; j < temp.size(); j++)
s.insert(temp[j]);
}
cnt++;
}
}
if(cnt >= 2) {
printf("Error: %d components", cnt);
} else {
temp.clear();
maxheight = 0;
fill(visit, visit + 10010, false);
dfs(s1, 1);
for(int i = 0; i < temp.size(); i++)
s.insert(temp[i]);
for(auto it = s.begin(); it != s.end(); it++)
printf("%d\n", *it);
}
return 0;
}
