Deepest Root (25)

从任意一个节点开始进行深度优先遍历，找到离他最远的节点（可能不止一个，记为集合A）；第二步：再从A中任意选一个节点出发进行深度优先遍历，找到离他最远的节点（记为集合B），最后最深根就是这两个集合的并集。

证明：第一步找出的节点一定是全局的最深根。

1     根据全局最优解一定是局部最优解的原理：最后全局的最深根一定也是某个局部最优解，比如：因为全局最深的根是固定的，不失一般性，我们就把他们标为1、2、3、4、5，那么从图中中任意一点出发，例如A，从他出发找到的局部最优解一定是在1、2、3、4、5，反之，如不在，也就是说有比1、2、3、4、5更深的节点，我们假设它存在并且成为B,那么可想而知，从1到B肯定要比从1到2要深，这就与1、2、3、4、5是全局最优解矛盾，所以假设不成立。原命题成立。即局部最优解一定在1、2、3、4、5中。

2    由第一步知道局部最优解是固定的，且全局最优解是局部最优解，根据这两条结论，得出：第一次遍历得到的最深的节点就是最深根

package go.jacob.day1017;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 1021. Deepest Root (25)
 * 
 * @author Jacob 一共N个点，有N-1条边。只要components大于1，必定有环。
 *         寻找最远距离的时候，只要使用两次DFS就可以了。原因如下： 树中最远的距离必是距离根节点R最远和次远的两个叶节点的连线。
 *         可以任意选择一个节点，进行深度优先搜索，第一次找到最远的节点。 用刚刚找到的最远节点为根节点做dfs，再次寻找最远节点（可能有多个）
 */
public class Demo1 {
    static int components = 0;
    static int n;
    static ArrayList<Integer>[] matrix;
    static boolean[] visited;
    static int[] deep;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        matrix = new ArrayList[n + 1];
        for (int i = 1; i < n + 1; i++) {
            matrix[i] = new ArrayList<Integer>();
        }
        visited = new boolean[n + 1];
        deep = new int[n + 1];
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            matrix[a].add(b);
            matrix[b].add(a);
        }
        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {
                dfs(i, i);
                components++;
            }
        }
        if (components == 1) {// 说明输入正常
            Queue<Integer> queue = new LinkedList<Integer>();
            ArrayList<Integer> list = new ArrayList<Integer>();
            queue.add(1);
            initVisited(visited);
            visited[1] = true;
            int max = getDeep(queue, 1);
            // 找到最远节点，加入到list中
            for (int i = 1; i < n + 1; i++){
                if (deep[i] == max){
                    list.add(i);
                }
            }
            initVisited(visited);
            max = list.get(0);
            visited[max] = true;
            queue.add(max);
            max = getDeep(queue, max);
            for (int i = 1; i < n + 1; i++){
                if (deep[i] == max && !list.contains(i)){
                    list.add(i);
                }
            }
            Collections.sort(list);
            for (Integer v : list)
                System.out.println(v);

        } else {
            System.out.println("Error: " + components + " components");
        }
        sc.close();
    }

    /*
     * 获得当前树的最深深度
     */
    private static int getDeep(Queue<Integer> queue, int end) {
        int level = 1;
        int tmpEnd=end;
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            for (Integer v : matrix[tmp]) {
                if (!visited[v]) {
                    deep[v] = level;
                    queue.offer(v);
                    visited[v] = true;
                    tmpEnd=v;
                }
            }
            if (!queue.isEmpty()&&tmp == end) {
                end = tmpEnd;
                level++;
            }
        }
        return level-1;
    }

    /*
     * 初始化visited矩阵（设置为false）
     */
    private static void initVisited(boolean[] visited2) {
        for (int i = 1; i < n + 1; i++)
            visited[i] = false;
    }

    /*
     * 深度优先搜索
     */
    private static void dfs(int root, int pre) {
        visited[root] = true;
        for (Integer temp : matrix[root]) {
            if (temp.equals(pre))
                continue;
            if (!visited[temp])
                dfs(temp, root);
        }
    }
}

	

#include <cstdio>
#include <vector>
#include <string.h>
using namespace std;
const int MAXN=1e4+10;

int n;
vector<int> vex[MAXN];
bool visited[MAXN]={false},vis[MAXN];
int dfs(int root,int depth){
    int d,maxd=depth;
    vis[root]=true;
    for(int i=0;i<vex[root].size();++i)
        if(!vis[vex[root][i]]){
            d=dfs(vex[root][i],depth+1);
            if(maxd<d) maxd=d;
        }
    return maxd;
}
void dfs2(int root){
    visited[root]=true;
    for(int i=0;i<vex[root].size();++i)
        if(!visited[vex[root][i]]) dfs2(vex[root][i]);
}
int main()
{
    int a,b;
    scanf("%d",&n);
    if(n==1){printf("1");return 0;}
    for(int i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        vex[a].push_back(b);
        vex[b].push_back(a);
    }
    int cnt=0,depth,maxdepth=-1;
    vector<int> MaxDVex;
    for(int i=1;i<=n;++i)
        if(!visited[i]){
            dfs2(i);
            ++cnt;
        }
    if(cnt>1) printf("Error: %d components",cnt);
    else{
        for(int i=1;i<=n;++i){
            memset(vis,0,sizeof(vis));
            if(!vis[i] && vex[i].size()==1){
                ++cnt;
                depth=dfs(i,1);
                if(maxdepth<depth){
                    maxdepth=depth;
                    MaxDVex.clear();
                    MaxDVex.push_back(i);
                }else if(maxdepth==depth)
                    MaxDVex.push_back(i);
            }
        }
        for(int i=0;i<MaxDVex.size();++i)
            printf("%d\n",MaxDVex[i]);
    }
    return 0;
}

#include<string>

#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int findRoot2(int *tree,int i)

{

    if(tree[i]==-1)return i;

    else

    {

        int tmp = findRoot2(tree,tree[i]);

        tree[i]=tmp;

        return tmp;

    }

}

int maxlevel =0;

void dfs(vector<int> *result,int level,int startNode,bool *already)

{

    //if(result[startNode].size()<=0) return;

    already[startNode] = true;

    if(maxlevel<level)

    {

        maxlevel = level;

    }

    for(int i=0;i<result[startNode].size();i++)

    {

        if(!already[result[startNode][i]])

        {

            int current = level+1;

            dfs(result,current,result[startNode][i],already);

        }

    }

}

int main()

{

    int N;

    scanf("%d",&N);

    int *tree = new int[N+1];

    vector<int> *result = new vector<int>[N+1];

    for(int i=1;i<=N;i++)

    {

        tree[i]=-1;

    }

    if(N==1)

    {

        int a,b;

        scanf("%d %d",&a,&b);

        cout<<a<<endl;

        return 0;

    }

    for(int i=1;i<=N-1;i++)

    {

        int a,b;

        scanf("%d %d",&a,&b);

        result[a].push_back(b);

        result[b].push_back(a);

        a=findRoot2(tree,a);

        b=findRoot2(tree,b);

        if(a!=b)

        {

            tree[a]=b;

        }

        }

    int sum=0;

    for(int j=1;j<=N;j++)

    {

        if(tree[j]==-1)

            sum++;

    }

    map<int,vector<int>> deep;

        bool *already = new bool[N+1];

    if(sum>1)

    {

        cout<<"Error: "<<sum<<" components"<<endl;

        return 0 ;

    }

    else

    {

        //寻找最大的深度的root id

        for(int i=1;i<=N;i++)

        {

            //深度遍历叶结点

            if(result[i].size()==1)

            {

                maxlevel = 1;

                for(int k=1;k<=N;k++)

                {

                    already[k]=false;

                }

                already[i]=true;

                dfs(result,0,i,already);

                deep[maxlevel].push_back(i);

            }

        }

    }

    int max=0;

    for(map<int,vector<int>>::iterator it=deep.begin();it!=deep.end();it++)

    {

        if(it->first>max)

        {

            max=it->first;

        }

    }

    sort(deep[max].begin(),deep[max].end());

    for(int i=0;i<deep[max].size();i++)

    {

        cout<<deep[max][i]<<endl;

    }

    return 0;

}

//方法1（此方法在数据量大时会超时）
#include <iostream>                      
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=10010;
vector<int> Adj[maxn],ans;
bool vis[maxn]={false};
int n,v1,v2,temp,block,deepest=0;
void DFS(int u,int depth){
    vis[u]=true;
    if(depth>temp) temp=depth;           //temp为当前点i为根时的最大深度
    for(int i=0;i<Adj[u].size();i++){
        int v=Adj[u][i];
        if(vis[v]==false)
            DFS(v,depth+1);
    }
}
void DFSTrave(int root){
    DFS(root,1);                        //从当前点i(传入为root)开始遍历
    block++;
    for(int u=1;u<=n;u++){
        if(vis[u]==false){
            DFS(u,1);
            block++;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&v1,&v2);
        Adj[v1].push_back(v2);
        Adj[v2].push_back(v1);
    }
    for(int i=1;i<=n;i++){
        temp=0;
        block=0;
        fill(vis,vis+maxn,false);
        DFSTrave(i);                   //每次从不同点开始遍历
        if(block==1){                  //n个点n-1条边的连通图必为树
            if(temp==deepest) ans.push_back(i); //本次遍历得到的树深度与最大深度相同
            else if(temp>deepest){
                deepest=temp;
                ans.clear();
                ans.push_back(i);
            }
        }
        else{                          //若图不连通
            printf("Error: %d components\n",block);
            break;
        }
    }
    if(ans.size()!=0){
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++)
            cout<<ans[i]<<endl;
    }
    return 0;
}


//方法2 //全局最优解是局部最优解，第一次遍历得到的最深的结点就是最深根 //由于从最深根出发到最深的叶子节点是相互对称的，所以我们再从当前的最深根出发遍历一次得到其他的最深根，再去重。  #include <iostream>                       
#include <vector>                        
#include <algorithm>
#include <set>
using namespace std;
const int maxn=10010;
vector<int> Adj[maxn],temp,ans;
set<int> s;                               //用set不用排序，不用去重
bool vis[maxn]={false};
int n,v1,v2,block=0,deepest=0;
void DFS(int u,int depth){
    vis[u]=true;
    if(depth==deepest) ans.push_back(u);
    else if(depth>deepest){               //若当前深度比最大树高大
        deepest=depth;
        ans.clear();
        ans.push_back(u);
    }
    for(int i=0;i<Adj[u].size();i++){
        int v=Adj[u][i];
        if(vis[v]==false)
            DFS(v,depth+1);
    }
}
void DFSTrave(int root){
    DFS(root,1);                         //从当前点i(传入为root)开始遍历
    block++;
    for(int u=1;u<=n;u++){
        if(vis[u]==false){
            DFS(u,1);
            block++;
        }        
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&v1,&v2);
        Adj[v1].push_back(v2);
        Adj[v2].push_back(v1);
    }
    DFSTrave(1);                        //先从点1开始一次遍历
    if(block==1){                       //n个点n-1条边的连通图必为树
        temp=ans;                       //让temp先保存第一次遍历时离根最远的结点集合
        ans.clear();
        fill(vis,vis+maxn,false);
        DFSTrave(temp[0]);              //从任意一个第一次遍历所得的最远结点开始第二次遍历
    }
    else {                              //若图不连通
        printf("Error: %d components\n",block);
        return 0;
    }
    for(int i=0;i<temp.size();i++)      //将两次遍历所得的结点插入set中（自动去重并排序）
        s.insert(temp[i]);
    for(int i=0;i<ans.size();i++)
        s.insert(ans[i]);
    for(auto i=s.begin();i!=s.end();i++)
        cout<<*i<<endl;
    return 0;
} 

// 1021_Deepest_Root.cpp: 定义控制台应用程序的入口点。
//



#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
//----------定义图
struct vexNode {  vector<int> Edge;
};
vector<vexNode> G;

int cnt; //结点计数
bool *visit;// 访问数组
int *h;// 每个结点为根的 高度数组
int highest=0;//最高用于比较

void Dfs(int s,int h,int&hest) {  if (visit[s] == true) { return; }  visit[s] = true;  if (h > hest) {// DFS 求最大深度  hest = h;  }  for (int i = 0; i < G[s].Edge.size(); i++) {  if (visit[G[s].Edge[i]] == false) {  Dfs(G[s].Edge[i],h+1,hest);  }  }
}
int DFSTravle(int s, int &high) {// 在对整张图dfs 的过程中求连通分量。  int components = 0;// 联通分量  if (visit[s] == false) {// 先从起始点开始一次dfs  Dfs(s, 1, high); components++;  }  int t = 0;  for (int i = 1; i <= cnt; i++)// 在对整张图dfs 求得连通分量  {  if (visit[i] == false) {  Dfs(i, 1, t); components++;  }  }  return components;
}
int main()
{  cin >> cnt;  for (int i = 0; i <=cnt; i++) {  G.push_back(vexNode());  }  for (int i = 0; i < cnt-1; i++) {  int f, t;  cin >> f >> t;  G[f].Edge.push_back(t);  G[t].Edge.push_back(f);  }  visit = new bool[cnt+1];    h = new int[cnt+1];  for (int i = 1; i <=cnt; i++) { h[i] = 0; }  for (int i = 1; i <=cnt; i++) {// 对没个结点都做一次DFS  for (int j = 1; j <=cnt; j++) {  visit[j] = false;  }  int comp = DFSTravle(i,h[i]);//  得到连通分量和 对应节点的最高的深度  if (comp!= 1) {  //多个连通分liang  cout << "Error: " << comp << " components";  return 0;  }  }  vector<int> high;  int best = -1;  for (int i = 1; i <= cnt; i++) {//  选出最大深度的结点（多个 ）  if (h[i] >= best) {  if (h[i] > best) {  high.clear();  }  high.push_back(i);  best = h[i];  }  }  vector<int>::iterator it = high.begin();  for (; it != high.end(); it++) {  cout << *it << endl;  }
    return 0;
} 

//两次dfs就能确定所有的最深结点
#include <cstdio>
#include <vector>
#include <cstring>
#include <set>
using namespace std;
const int maxn = 10000 + 10;

vector<int> graph[maxn];
int fa[maxn], visited[maxn] = {0};
int height[maxn] = {0}, max_height = 0;
set<int> out_node;

void init(int num){
    for(int k=1; k<=num; k++)
        fa[k] = k;
}

int find_fa(int x){ 
    while(x != fa[x])
        x = fa[x];
    return x;
}

void Union(int x, int y){
    x = find_fa(x);
    y = find_fa(y);
    if(x != y) fa[x] = y;
}

int Components_num(int num){ 
    set<int> s;
    for(int i=1; i<=num; i++){
        int set_id = find_fa(i);
        if(s.count(set_id) == 0)
            s.insert(set_id);
    }
    return s.size();
}

void Dfs(int s){
    visited[s] = 1;
    for(unsigned int i=0; i<graph[s].size(); i++){
        int v = graph[s][i];
        if(visited[v]) continue;
        height[v] = height[s] + 1;
        max_height = (max_height > height[v]) ? max_height : height[v];
        Dfs(v);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    init(n);
    for(int i=0; i<n-1; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
        Union(u, v);
    }
    int cnm = Components_num(n);
    if(cnm > 1) 
        printf("Error: %d components\n", cnm);
    else{
        height[1] = 0;
        Dfs(1);
        for(int i=1; i<=n; i++){
            if(height[i] == max_height)
                out_node.insert(i);
        }
        max_height = 0;
        memset(height, 0, sizeof(height));
        memset(visited, 0, sizeof(visited));
        int s = *(out_node.begin());
        Dfs(s);
        for(int i=1; i<=n; i++){
            if(height[i] == max_height)
                out_node.insert(i);
        }
        for(auto iter=out_node.begin(); iter!=out_node.end(); iter++)
            printf("%d\n", *iter);
    }
    return 0;
}

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <set>

using namespace std;

const int maxn=10005;

vector<int> map[maxn]; //邻接表

//**************并查集计算连通图个数****************//

int father[maxn];

//*****************初始化并查集*****************//

void init(int n){

    for (int i=0; i < n; ++i) {

        father[i] = i;

    }

}

//********************查找根节点*******************//

int getfather(int x){

    if (x != father[x]) {

        father[x] = getfather(father[x]);

    }

    return father[x];

}

//*********合并两个元素所在的集合,返回是否有环*********//

void Union(int x,int y){

    x = getfather(x);

    y = getfather(y);

    if (x != y) {

        father[x] = y;

    }

}

//*****************并查集结束****************//

//*************DFS**************//

vector<int> visited;

int deepest;

set<int> res;

void DFS(int i,int distance){

    if (distance > deepest) {

        res.clear();

        res.insert(i);

        deepest = distance;

    }

    else if (distance == deepest){

        res.insert(i);

    }

    visited[i] = 1;

    for (int j=0; j < map[i].size(); ++j) {

        if (!visited[map[i][j]]) {

            visited[map[i][j]] = 1;

            DFS(map[i][j],distance+1);

            visited[map[i][j]] = 0;

        }

    }

    visited[i] = 0;

}

int main(){

    int N,from,to;

    cin >> N;

    init(N);    //初始化并查集

    for (int i=1; i < N; ++i) {

        cin >> from >> to;

        Union(from,to);

        map[from].push_back(to);

        map[to].push_back(from);

    }

    int Sum_huan = 0;   //连通分量的个数

    for (int i=1; i < N; ++i) {

        if (father[i]==i) {

            Sum_huan++;

        }

    }

    visited.resize(N+1, 0);

    if (Sum_huan > 1) {

        cout << "Error: " << Sum_huan << " components" <<endl;

        return 0;

    }

    set<int> trees;

    //****************随便找个点1开始第一次深度搜索找到最远的点*****************//

    DFS(1, 1);

    //******************第一次找到的点一定是最后需要的那个根节点之一*************//

    for (auto it = res.begin(); it != res.end(); ++it) {

        trees.insert(*it);

    }

    //****************从最远的点开始第二次搜索******************//

    int point = (*res.begin());

    DFS(point, 1);

    for (auto it = res.begin(); it != res.end(); ++it) {

        trees.insert(*it);

    }

    for (auto it = trees.begin(); it != trees.end(); ++it) {

        cout << *it << endl;

    }

    return 0;

}

#include<bits/stdc++.h>
using namespace std;

const int Max=10010;
int father[Max];
int height[Max];
int n;
vector<int> G[Max],tmp,ans;

void Initial() {
	for(int i=1; i<=n; i++) {
		father[i]=i;
		height[i]=1;
	}
}

int Find(int x) {
	if(x!=father[x]) {
		father[x]=Find(father[x]);
	}
	return father[x];
}

void Union(int x,int y) {
	x=Find(x);
	y=Find(y);
	if(x!=y) {
		if(height[x]>height[y]) {
			father[y]=x;
		} else if(height[x]<height[y]) {
			father[x]=y;
		} else {
			father[x]=y;
			height[y]++;
		}
	}
}

int Maxh=0;
void DFS(int id,int h,int f) {
	if(h>Maxh) {
		tmp.clear();
		tmp.emplace_back(id);
		Maxh=h;
	} else if(h==Maxh) {
		tmp.emplace_back(id);
	}
	for(int i=0; i<G[id].size(); i++) {
		if(G[id][i]==f) continue;
		DFS(G[id][i],h+1,id);
	}
}

int main() {
	int a,b;
	scanf("%d",&n);
	Initial();
	for(int i=1; i<n; i++) {
		scanf("%d %d",&a,&b);
		G[a].emplace_back(b);
		G[b].emplace_back(a);
		Union(a,b);
	}
	int count=0;
	for(int i=1; i<=n; i++) {
		if(i==Find(i)) {
			count++;
		}
	}
	if(count>1) {
		printf("Error: %d component\n",count);
		return 0;
	} else {
		DFS(1,1,-1);
		ans=tmp;
		DFS(ans[0],1,-1);
		for(int i=0; i<tmp.size(); i++) {
			ans.emplace_back(tmp[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]);
		}
	}
	return 0;
}

//bfs宽度优先 
#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
#include<set>

using namespace std;

int main()
{     set<int> node_set;     map<int, set<int> > edge_map;     queue<int> node_queue;     int count = 0;//树的数量      int pre[10001] = {0};     int pre2[10001] = {0};          int N = 0;     cin>>N;          for (int i = 0; i < N-1; i++)     {         int a,b;         scanf("%d %d",&a,&b);
//        if (node_set.find(a) == node_set.end())
//            node_set.insert(a);
//        if (node_set.find(b) == node_set.end())
//            node_set.insert(b);         node_set.insert(i+1);                          edge_map[a].insert(b);         edge_map[b].insert(a);     }          node_set.insert(N);          bool is_tree = true;     int node_front;     int level = -1;     set<int> final_level;     while (!node_set.empty())      {         count ++;         int node = *node_set.begin();         node_queue.push(node);         node_queue.push(level);         final_level.insert(node);                          while(!node_queue.empty()){             node_front = node_queue.front();                          if (node_front < 0) {                 level --;                 node_queue.pop();                 if (!node_queue.empty()){                     final_level.clear();                     node_queue.push(level);                 }                 continue;             }                          final_level.insert(node_front);             node_set.erase(node_front);                          set<int>::iterator iter = edge_map[node_front].begin();             for(; iter != edge_map[node_front].end();iter++){                 if (*iter == pre[node_front])                     continue;                 if (node_set.find(*iter) != node_set.end()) {                     if (pre[*iter] != 0) {                         is_tree = false;                         continue;                     }                     pre[*iter] = node_front;                     node_queue.push(*iter);                     } else                      is_tree = false;                      }             node_queue.pop();         }     }          if (!is_tree){         cout<<"Error: "<<count<<" components";      } else {         int level2 = -1;         set<int> final2;         node_front = *final_level.begin();                  node_queue.push(node_front);          node_queue.push(level2);                           while(!node_queue.empty()) {             node_front = node_queue.front();                                          if (node_front < 0) {                 level2 --;                 node_queue.pop();                 if (!node_queue.empty()){                     final2.clear();                     node_queue.push(level2);                 }                 continue;             }                          final2.insert(node_front);                          set<int>::iterator iter = edge_map[node_front].begin();             for(; iter != edge_map[node_front].end();iter++){                 if (*iter == pre2[node_front])                     continue;                 pre2[*iter] = node_front;                 node_queue.push(*iter);                 }             node_queue.pop();         }         for (set<int>::iterator iiit = final2.begin(); iiit != final2.end(); iiit++)             if (final_level.find(*iiit) == final_level.end())                 final_level.insert(*iiit);                  for (set<int>::iterator it = final_level.begin(); it != final_level.end(); ){             cout<<*it;             if (++it != final_level.end())                 cout<<endl;         }                           cout<<endl;      }                    return 0;
} 

思路： 参考大佬
对于并查集推荐 https://blog.csdn.net/u013546077/article/details/64509038
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <fstream>
using namespace std;

const int size = 10000;

#ifndef debug
ifstream ifile("case.txt");
//freopen ("case.txt","r",stdin);
#define cin ifile
#endif

class DisjointSet
{
private:
    int *T, size, sum;
    int FindRoot(int i)
    {
        return T[i] < 0 ? i : (T[i] = FindRoot(T[i]));
    }
public:
    DisjointSet(int _size) :size(_size)
    {
        T = new int[size];
        Init();
    }
    void Init()
    {
        sum = size;
        memset(T, -1, sizeof(int)*size);
    }
    bool Unioned(int i, int j)
    {
        return FindRoot(i) == FindRoot(j);
    }
    void Union(int i, int j)//合并领导层
    {
        if ((i = FindRoot(i)) != (j = FindRoot(j)))// 不是连通的把一个领导层换掉
        {
            T[i] = T[i] + T[j];
            T[j] = i;
            sum--;
        }//如果是连通的就不用做任何事情
    }
    int FindSum(int i)// 返回所有的节点的深度
    {
        return -T[FindRoot(i)];
    }
    int SumOfUnits()// 返回没有来连通的个数。
    {
        return sum;
    }
    ~DisjointSet()
    {
        delete[] T;
    }
};

vector<int> v[10000];// 这种存储方式是存储的孩子节点
int vis[10000];
void dfs(int i, int dist, int & Max)
{
    vis[i] = dist;
    Max = max(Max, vis[i]);
    for (int k = 0; k < v[i].size(); k++)
    {
        if (vis[v[i][k]] == -1)
        {
            dfs(v[i][k], dist + 1, Max);
        }
    }
}

int main()
{
    int i, j, temp;
    int n;
    cin >> n;
    DisjointSet ds(n);
    for (i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        v[a].push_back(b);
        v[b].push_back(a);
        ds.Union(a, b);// 合并领导层这么说他们是连通的
    }
    if (ds.SumOfUnits() == 1)// 全部是在一个连通图里面
    {
        int start, Max;
        set<int> s;
        for (Max = start = i = 0; i < 2; i++)// 遍历两边就可以得到全部的最长的节点
        {
            memset(vis, -1, sizeof(vis));// 因为要遍历两次所以清空一下。
            dfs(start, 0, Max);
            for (j = 0; j < n; j++)
            {
                if (vis[j] == Max)// 记录层数量，如果是叶子层且节点最深那么就把她们记录下来
                {
                    s.insert(j);
                }
            }
            start = *s.begin();// 这个点可以任意取一个值
        }
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
            printf("%d\n", (*it) + 1);
        }
    }
    else// 如果不是一棵连通图那么就输出总共连通的单位
    {
        printf("Error: %d components\n", ds.SumOfUnits());
    }
    system("pause");
    return 0;
    
}

--------------------------------------
直接使用两个DFS即可
一个计算树高一个计算真正的最高的root。  计算最高的root 参考  别人的博客。
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;

const int maxn = 10010;
vector<int> v[maxn];
bool visit[maxn];
int maxH = 0;
vector<int> temp;
vector<int> ans;
set<int> s;
void DFS(int x){
    if(visit[x] == true){
        return;
    }
    visit[x] = true;
    for(int i=0; i<v[x].size(); i++){
        DFS(v[x][i]);
    }
}


void DFS1(int x,int height){
    if(visit[x] == true){
        return;
    }
    visit[x] = true;
    if(height > maxH){
        temp.clear();
        maxH = height;
        temp.push_back(x);
    }else if(maxH == height){
        temp.push_back(x);
    }
    for(int i=0; i<v[x].size(); i++){
        DFS1(v[x][i], height+1);
    }
}



int main(){
    //freopen("case.txt","r",stdin);
    int N;
    scanf("%d",&N);
    int a,b;
    // 初始化连通集
    //init();
    for(int i=1; i<N; i++){
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    memset(visit, false, sizeof(visit));
    int count = 0;
    for(int i=1; i<= N; i++){
        if(!visit[i]){
            DFS(i);
            count++;
        }
    }
    if(count > 1){
        printf("Error: %d components\n",count);
        return 0;
    }else{
        memset(visit, false, sizeof(visit));
        DFS1(1,1);
        memset(visit, false, sizeof(visit));
        ans = temp;
        DFS1(ans[0],1);
        for(int i=0; i<temp.size(); i++){
            s.insert(temp[i]);
        }
        for(int i=0; i<ans.size(); i++){
            s.insert(ans[i]);
        }
        for(set<int>::iterator i=s.begin(); i != s.end(); i++){
            /*if(i == s.begin()){
                printf("%d",*i);
            }else{
                printf(" %d",*i);
            }*/
            printf("%d\n",*i);
        }
    } 
}

	

#include<cstring>
#include<cstdio>
#include<vector>
#include<set>
#include<iostream>
using namespace std;
const int maxn=10010;
vector<int> G[maxn];
int  N;
int father[maxn];
bool vis[maxn]={false};
set<int> temp,ans;
void init()
{
    for(int i=1;i<=N;i++)
     {
            father[i]=i;
            vis[i]=false;
     }
}
int findFather(int x)
{
    int a=x;
    while(x!=father[x])
        x=father[x];
    //father[a]=x
    while(a!=father[a])
    {
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
void Union(int u,int v)
{
    int fau=findFather(u);
    int fav=findFather(v);
    if(fau!=fav)
        father[fau]=fav;
}
int maxHeight=0;
void DFS(int root,int height)
{
    vis[root]=1;
    if(height>maxHeight)
    {
        temp.clear();
        temp.insert(root);
        maxHeight=height;
    }
    if(height==maxHeight)
    {
        temp.insert(root);
    }
    for(int i=0;i<G[root].size();i++)
        if(vis[G[root][i]]==false)
           DFS(G[root][i],height+1);
}
int main()
{
    cin>>N;
    init();
    for(int i=1;i<=N-1;i++)
    {
        int c1,c2;
        cin>>c1>>c2;
        G[c1].push_back(c2);
        G[c2].push_back(c1);
        Union(c1,c2);
    }
    int block=0;
    for(int i=1;i<=N;i++)
    {
        int fa=findFather(i);
        if(vis[fa]==false)
        {
            block++;
            vis[fa]=true;
        }
    }
    if(block!=1) cout<<"Error: "<<block<<" components"<<endl;
    else
    {
       memset(vis,0,sizeof(vis));
       DFS(1,1);
       ans=temp;
       memset(vis,0,sizeof(vis));
       DFS(*(ans.begin()),1);
       set<int>::iterator it;
       for(it=temp.begin();it!=temp.end();it++)
           ans.insert(*it);
       for(it=ans.begin();it!=ans.end();it++)
            cout<<*it<<endl;
    }
}