PAT甲级1021Deepest Root

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805482919673856

题解

题目要求

• 输入
  • N：正整数，不超过10000，结点的数量，索引为[1,N]
  • N-1条边
• 输出
  • 输出深度最大的根结点，如果不唯一，则按升序输出。如果这个图不是树，则输出图中连通分量的数量

方法一

解题思路

• 没有回路的无向图是连通的当且仅当它是树

1. 求该图的连通分量数，如果连通分量数大于1，则输出连通分量数，程序终止；
2. 对于每一个结点，将其作为根结点，通过dfs求其高度depth，将depth与全局最大高度maxDepth比较，并更新全局最大高度及其对应根结点；
3. 输出根结点

代码

如果用邻接矩阵，则第3个点会超时，用邻接表则不超时。

// Problem: PAT Advanced 1021
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805482919673856
// Tags: 树 图 连通分量 连通图 DFS

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 10001;
int n, tempDepth = 0, depth = 0, maxDepth = 0;
vector<int> deepestRoot;
vector<vector<int>> v;
bool visited[MAXN];

void dfs(int u){
    visited[u] = true;
    tempDepth += 1;

    if (depth < tempDepth){
        depth = tempDepth;
    }
    for(int i = 0; i < v[u].size(); i++){
        if (!visited[v[u][i]]){
            dfs(v[u][i]);
        }
    }

    tempDepth -= 1;
}

int main()
{
    scanf("%d", &n);
    v.resize(n+1);
    int v1, v2;
    for (int i = 0; i < n - 1; i++){
        scanf("%d %d", &v1, &v2);
        v[v1].push_back(v2);
        v[v2].push_back(v1);
    }

    int num = 0;
    for (int i = 1; i <= n; i++){
        if (!visited[i]){
            dfs(i);
            num++;
        }
    }
    if (num > 1){
        printf("Error: %d components", num);
        return 0;
    }
    else if (num == 1){
        for (int root = 1; root <= n; root++){
            fill(visited + 1, visited + 1 + n, false);
            depth = 0;
            dfs(root);
            if (maxDepth < depth){
                maxDepth = depth;
                deepestRoot.clear();
                deepestRoot.push_back(root);
            }
            else if (maxDepth == depth){
                deepestRoot.push_back(root);
            }
        }

        for (int i = 0; i < deepestRoot.size(); i++){
            printf("%d\n", deepestRoot[i]);
        }
    }
    
    return 0;
}

方法二

思路

1. 第一次DFS：判断连通分量数量，如果超过1，则直接输出，程序结束

   同时保存深度最大的那些结点到数组s中

2. 第二次DFS：从s中的任一个结点出发进行DFS，此时深度最大的结点与s的并集就是结果

这个思路很妙，并且速度很快：这是无向图，是双向的，所以正序倒序各求一遍合起来就是结果。

代码

// Problem: PAT Advanced 1021
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805482919673856
// Tags: 树 图 连通分量 连通图 DFS set

#include <iostream>
#include <vector>
#include <set>
using namespace std;

const int MAXN = 10001;
int n, depth = 0, maxDepth = 0;
vector<int> temp;
set<int> result;
vector<vector<int>> v;
bool visited[MAXN];

void dfs(int u){
    visited[u] = true;
    depth += 1;

    if (maxDepth < depth){
        maxDepth = depth;
        temp.clear();
        temp.push_back(u);
    }
    else if (maxDepth == depth){
        temp.push_back(u);
    }
    for(int i = 0; i < v[u].size(); i++){
        if (!visited[v[u][i]]){
            dfs(v[u][i]);
        }
    }

    depth -= 1;
}

int main()
{
    scanf("%d", &n);
    v.resize(n+1);
    int v1, v2;
    for (int i = 0; i < n - 1; i++){
        scanf("%d %d", &v1, &v2);
        v[v1].push_back(v2);
        v[v2].push_back(v1);
    }

    int num = 0;
    for (int i = 1; i <= n; i++){
        if (!visited[i]){
            dfs(i);
            num++;
        }
    }

    if (num > 1){
        printf("Error: %d components", num);
        return 0;
    }
    else if (num == 1){
        for (int i = 0; i < temp.size(); i++)
            result.insert(temp[i]);
        
        fill(visited + 1, visited + 1 + n, false);
        int u = temp[0];
        temp.clear();
        dfs(u);
        for (int i = 0; i < temp.size(); i++)
            result.insert(temp[i]);
        for (auto it = result.begin(); it != result.end(); it++)
            printf("%d\n", *it);
    }

    return 0;
}

参考链接

https://blog.csdn.net/liuchuo/article/details/52294178

---

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

---