[PAT解题报告] Deepest Root

给定一棵树（无向无环图）——先判断给定的到底是不是树，如果是树，以那些节点为根能得到的尽可能高的树。

分析：判断是否是树比较简单，可以用dfs, bfs求连通分量，如果是1就是树，当然我采取的是并查集，类似kruskal算法加边，顺便统计连通分量的个数。然后有两种办法处理。一种是暴力——比较好理解，以每个节点为根dfs一次求出高度。这种算法的时间复杂度是O(n²)，好在n不大10000，这种暴力可以通过。

代码：

#include <cstdio> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <set> 
using namespace std; 

int f[100005]; 
vector<int> con[100005];
vector<int> v;
int c,maxd;

int getf(int x) {
    return f[x] = ((x == f[x])?x:getf(f[x]));
}

void make(int x,int y) {
    x = getf(x);
    y = getf(y);
    if (x != y) {
        f[x] = y;
        --c;
    }
}

int dfs(int x,int father) {
    int  d = 0;
    for (int i = 0; i < con[x].size(); ++i) {
        if (con[x][i] != father) {
            d = max(d, dfs(con[x][i], x));
            
        }
    }
    return d + 1;
}


int main() {
int n;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        f[i] = i;
    }
    c = n;
    for (int i = n - 1; i; --i) {
        int x,y;
        scanf("%d%d",&x,&y);
        make(--x, --y);
        con[x].push_back(y);
        con[y].push_back(x);
    }
    if (c > 1) {
        printf("Error: %d components\n",c); 
    }
    else { 
        int depth = 0;
        for (int i = 0; i < n; ++i) {
            depth = max(depth, dfs(i, -1));
        }
        for (int i = 0; i < n; ++i) {
            if (dfs(i, - 1) == depth) {
                printf("%d\n", i + 1) ;
            }
        }
    }
    return 0; 
}

另外一种算法比较巧妙，先从任意一个点dfs，可以得到一些点距离这个点最远，再从第一次dfs保存这些点中的任意一个dfs，得到距离它最远的点，两次得到的全部点就是答案。这种算法的时间复杂度直接降为O(n)——关键要理解一个结论到达树中最远的两个点可以通过两次dfs得到。

代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
using namespace std;

int f[100005];
vector<int> con[100005];
vector<int> v;
int c,maxd;

int getf(int x) {
    return f[x] = ((x == f[x])?x:getf(f[x]));
}

void make(int x,int y) {
    x = getf(x);
    y = getf(y);
    if (x != y) {
        f[x] = y;
        --c;
    }
}

void dfs(int x,int father,int dep) {
    if (dep > maxd) {
        maxd = dep;
        v.resize(1);
        v[0] = x;
    }
    else if (dep == maxd) {
        v.push_back(x);
    }
    for (int i = 0; i < con[x].size(); ++i) {
        if (con[x][i] != father) {
            dfs(con[x][i], x , dep + 1);
        }
    }
}


int main() {
    scanf("%d",&c);
    for (int i = 0; i < c; ++i) {
        f[i] = i;
    }
    for (int i = c - 1; i; --i) {
        int x,y;
        scanf("%d%d",&x,&y);
        make(--x, --y);
        con[x].push_back(y);
        con[y].push_back(x);
    }
    if (c > 1) {
        printf("Error: %d components\n",c);
    }
    else {
        maxd = -1;
        dfs(0, -1, 0);
        set<int> all;
        for (int i = 0; i < v.size(); ++i) {
            all.insert(v[i]);
        }
        maxd = -1;
        dfs(v[0], -1, 0);
        for (int i = 0; i < v.size(); ++i) {
            all.insert(v[i]);
        }
        for (set<int>::iterator t = all.begin(); t != all.end(); ++t) {
            printf("%d\n",(*t) + 1);
        }
    }
    return 0;
}

原题链接： http://www.patest.cn/contests/pat-a-practise/1021