【PAT】1021. Deepest Root (25)

題目

連結：​​https://www.patest.cn/contests/pat-a-practise/1021​​

A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

nput Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N-1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.

Output Specification:

For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print “Error: K components” where K is the number of connected components in the graph.

Sample Input 1:

5

1 2

1 3

1 4

2 5

Sample Output 1:

3

4

5

Sample Input 2:

5

1 3

1 4

2 5

3 4

Sample Output 2:

Error: 2 components

分析

題意：

1. 是一棵樹嘛？

   否，則輸出有幾棵樹

2. 找到最深(高)的樹的root

   比如 sample 1：

   以 3, 4, 5為root, 均擁有最深的樹

   以升序方式輸出

判斷是否為同一棵樹（并查集）

int par[MAXN];

int find(int x) {
    if (par[x] == x)
        return x;
    else
        return par[x] = find(par[x]);
}

void unite(int x, int y) {

    x = find(x) ;
    y = find(y) ;

    if (x == y) return      

（2）dfs

int dfs(int n) {

    flag[n] = 1;
    int ans = 0;

    for (int i = 0; i < graph[n].size(); ++i) {
        if (flag[graph[n][i]] == 0) {
            int temp = dfs(graph[n][i]);
            ans = max(temp, ans);
        }
    }
    return ans + 1;
}      

題解（已AC）

/**
    2018.1.28
    Donald
*/
//1021. Deepest Root (25)

/**
    無向連通圖 可以 構成一棵樹

    1. 是一棵樹嘛？
        否，則輸出有幾棵樹

    2. 找到最深(高)的樹的root
        比如 sample 1：
            以 3, 4, 5為root, 均擁有最深的樹

        以升序方式輸出

*/


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 10005

int N;
vector<int> graph[MAXN];
int par[MAXN];
int flag[MAXN];
int deep[MAXN];
int cnt;

int find(int x) {
    if (par[x] == x)
        return x;
    else
        return par[x] = find(par[x]);
}

void unite(int x, int y) {

    x = find(x) ;
    y = find(y) ;

    if (x == y) return ;

    par[x] = y;

}

int dfs(int n) {

    flag[n] = 1;
    int ans = 0;

    for (int i = 0; i < graph[n].size(); ++i) {
        if (flag[graph[n][i]] == 0) {
            int temp = dfs(graph[n][i]);
            ans = max(temp, ans);
        }
    }
    return ans + 1;
}

void init() {
    scanf("%d", &N);

    for (int i = 1; i <= N; ++i) {
        par[i] = i;
    }

    for (int i = 1; i < N; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
        unite(x, y);    // 因為x y互聯，so為同一棵樹
    }
}

bool isATree() {
    int components = 0;
    for (int i = 1; i <= N; ++i) {
        if (par[i] == i) {
            components ++;
        }
    }

    if (components > 1) {
        printf("Error: %d components\n", components);
        return false;
    }

    return true;
}

void findDeepestRoots() {
    int maxDeep = -1;

    for (int i = 1; i <= N; ++i) {
        cnt = 0;
        memset(flag, 0, sizeof(flag));
        deep[i] = dfs(i);

        if (deep[i] > maxDeep) {
            maxDeep = deep[i];
        }
    }

    for (int i = 1; i <= N; ++i) {
        if (deep[i] == maxDeep) {
            printf("%d\n", i);
        }
    }
}


int main(void) {

    init();

    if (!isATree()) {
        return 0;
    }

    findDeepestRoots();

    return 0;
}