[PAT] A1021 Deepest Root

【题目大意】

给出n个结点和n-1条边，问它们能否形成一棵n个结点的树，如果能，从中选出结点作为树根，使整棵树的高度最大。输出所有满足要求的可以作为树根的结点。

【思路】

方法一：模拟。

1 连通、边数为n-1的图一定是一棵树。因此先判断连通图个数（用DFS遍历图，从而计算连通图个数），等于1则能形成一棵树。

2 遍历每一个节点，假设它为根节点构造一棵树。

方法二： 

1 由于连通、边数为n-1的图一定是一棵树，因此需要判断给定数据是否能使图连通。
2 确定图连通后，则确定了树，选择合适根结点使树高最大的做法为：
先任意选择一个结点，从该节点开始遍历整棵树，获取能达到的最深的结点，记为集合A；然后从集合A中任意一个结点出发遍历整棵树，获取能达到的最深顶点，记为结点集合B。集合A与B的并集就是所求结果。

https://blog.csdn.net/hy971216/article/details/82252707

https://blog.csdn.net/qq_38677814/article/details/80859998

https://blog.csdn.net/sinat_29278271/article/details/47934611

 【tips】

1 非二叉树其实可以想象成一个特殊的图来解决。像这一题，用的其实全都是图的知识来解决，因为其考点不在父子关系上。

2 也可以使用并查集判断连通图个数（未实践过）：每读入一条边的两个端点，判断这两个端点是否属于相同的集合，如果不同，则将它们合并到一个集合中，当处理完所有边后根据最终产生的集合个数是否为1来判断给定的图是否连通。

【AC代码】

方法一：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define N 10002
vector<int>G[N];
int n;
int vis[N] = { false };
int level[N] = { 0 };
void DFS(int u)
{
    for (int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if (vis[v] == false)
        {
            vis[v] = true;
            DFS(v);
        }
    }
}
int BFS(int root)
{
    int mlevel = 0;
    queue<int>q;
    q.push(root);
    vis[root] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            if (vis[v] == false)
            {
                q.push(v);
                vis[v] = true;
                level[v] = level[u] + 1;
                if (level[v] > mlevel)
                    mlevel = level[v];
            }
        }
    }
    return mlevel;
}
int main()
{
    cin >> n;
    int i;
    for (i = 0; i < n - 1; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        G[t1].push_back(t2);
        G[t2].push_back(t1);
    }
    int tu = 0;
    for (i = 1; i <= n; i++)
    {
        if (vis[i] == false)
        {
            tu++;
            vis[i] == true;
            DFS(i);
        }    
    }
    if (tu > 1)
    {
        cout << "Error: " << tu << " components";
        return 0;
    }
    int maxLevel = 0;
    vector<int>ans;
    for (i = 1; i <= n; i++)
    {
        fill(vis, vis + N, false);
        fill(level, level + N, false);
        int ceng = BFS(i);
        if (ceng == maxLevel)
        {
            ans.push_back(i);
        }
        if (ceng > maxLevel)
        {
            ans.clear();
            ans.push_back(i);
            maxLevel = ceng;
        }
    }
    for (i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;

    return 0;
}

方法二：

#include<iostream>
#include<queue>
#include<vector>
#include<set>
using namespace std;
#define N 10002
vector<int>G[N];
int n;
bool vis[N] = { false };
int level[N] = { 0 };
void DFS(int u)
{
    for (int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if (vis[v] == false)
        {
            vis[v] = true;
            DFS(v);
        }
    }
}
int BFS(int root)
{
    int mlevel = 0;
    queue<int>q;
    q.push(root);
    vis[root] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            if (vis[v] == false)
            {
                q.push(v);
                vis[v] = true;
                level[v] = level[u] + 1;
                if (level[v] > mlevel)
                    mlevel = level[v];
            }
        }
    }
    return mlevel;
}
int main()
{
    cin >> n;
    int i;
    for (i = 0; i < n - 1; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        G[t1].push_back(t2);
        G[t2].push_back(t1);
    }
    int tu = 0;
    for (i = 1; i <= n; i++)
    {
        if (vis[i] == false)
        {
            tu++;
            vis[i] = true;
            DFS(i);
        }    
    }
    if (tu > 1)
    {
        cout << "Error: " << tu << " components";
        return 0;
    }

    fill(vis, vis + N, false);
    fill(level, level + N, 0);
    int maxlevel = BFS(1);
    set<int>ans;
    for (i = 1; i <= n; i++)
        if (level[i] == maxlevel)
            ans.insert(i);
    set<int>::iterator it = ans.begin();
    int v = *it;
    fill(vis, vis + N, false);
    fill(level, level + N, 0);
    maxlevel = BFS(v);
    for (i = 1; i <= n; i++)
        if (level[i] == maxlevel)
            ans.insert(i);
    for (it = ans.begin(); it != ans.end(); it++)
        cout << *it << endl;

    return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<vector>
using namespace std;
#define MAX 10002
#define INF 10000000
vector<int>Adj[MAX];
set<int>root, root1;
bool vis[MAX] = { false };
int n, maxlevel = 0;
void DFS(int x, int level) {
    vis[x] = true;
    if (level > maxlevel) {
        root.clear();
        root.insert(x);
        maxlevel = level;
    }
    else if (level == maxlevel)
        root.insert(x);
    for (int i = 0; i < Adj[x].size(); i++)
        if (vis[Adj[x][i]] == false)
            DFS(Adj[x][i], level + 1);
}
int Trave() {
    int i, times = 0;
    fill(vis, vis + n + 1, false);
    for (i = 1; i <= n; i++) {
        if (vis[i] == false) {
            maxlevel = 0;
            DFS(i, 0);
            times++;
        }
    }
    return times;
}
int main() {
    int i, a, b;
    scanf("%d", &n);
    for (i = 0; i < n - 1; i++) {
        scanf("%d%d", &a, &b);
        Adj[a].push_back(b);
        Adj[b].push_back(a);
    }
    int ans    = Trave();
    if (ans == 1) {
        root1 = root;
        auto it = root.begin();
        fill(vis, vis + n + 1, false);
        DFS(*it, 0);
        for (it = root1.begin(); it != root1.end(); it++)
            root.insert(*it);
        for (it = root.begin(); it != root.end(); it++)
            printf("%d
", *it);
    }
    else {
        printf("Error: %d components", ans);
    }
    return 0;
}