Zhao70's Blog

PAT1021 Deepest Root

发表于 | 分类于

题目大意

PAT1021 Deepest Root

给定一个图, 问是否为连通图, 若不是, 则输出连通分量的数目. 否则, 以任一个点为根, 求树的最大深度, 输出这些根节点.

思路

  1. 用并查集检查图是否的连通图.
  2. 从任意一点进行dfs, 得到一个集合, 该集合的点即为 deepest root 的一部分.
  3. 从上一步的集合中任意一点进行dfs, 得到一个集合.
  4. 答案集合 即为 2, 3步的合集.

证明

设任一点为 A , 从点 A 到其他点的最大距离为 Lx, Lx 为局部最优解答, 由于图是连通的, 图中任意一点都可以到达点 A , 且距离 Ly < Lx. 因此 第一次 dfs 得到的解 为 最终解 的 部分解.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstdio>
using namespace std;
int nNode;
struct Node{
    vector<int> nodeList;
};
const int arrSize = 10100;
int arr[arrSize];
bool isVis[arrSize];
vector<Node> edge(arrSize);
int getFather(int loc){
    if(arr[loc] == loc)
        return loc;
    loc = getFather(arr[loc]);
    return loc;
}
void merge(int a, int b){
    a = getFather(a);
    b = getFather(b);
    if(a < b)
        arr[b] = a;
    else
        arr[a] = b;
}
void init(){
    for(int i = 0; i <= nNode + 1; i++){
        arr[i] = i;
        isVis[i] = false;
    }
}
int getComponents(){
    int cnt = 0;
    for(int i = 1; i <= nNode; i++){
        if(arr[i] == i)
            cnt++;
    }
    return cnt;
}
set <int> ans;
int maxD = 0;
int dfs(int vertex, int depth){
    if(depth > maxD){
        ans.clear();
        maxD = depth;
    }
    if(depth == maxD)
        ans.insert(vertex);
    for(int i = 0; i < edge[vertex].nodeList.size(); i++){
        if(isVis[edge[vertex].nodeList[i]])
            continue;
        isVis[edge[vertex].nodeList[i]] = true;
        dfs(edge[vertex].nodeList[i], depth + 1);
    }
}
int main(){
    cin >>  nNode;
    if(nNode == 1){
        cout << 1 << endl;
        return 0;
    }
    init();
    for(int i = 0; i < nNode - 1; ++i){
        int a, b;
        cin >> a >> b;
        merge(a, b);
        edge[a].nodeList.push_back(b);
        edge[b].nodeList.push_back(a);
    }
    int cs = getComponents();
    if(cs != 1){
        cout << "Error: " << cs << " components" << endl;
        return 0;
    }
    init();
    isVis[1] = true;
    dfs(1, 0);
    init();
    isVis[*ans.begin()] = true;
    set<int> temp = ans;
    ans.clear();
    dfs(*temp.begin(), 0);
    for(set<int>::iterator it = temp.begin(); it != temp.end(); it++){
        ans.insert(*it);
    }
    for(set<int>::iterator it = ans.begin(); it != ans.end(); it++){
        cout << *it << endl;
    }
    return 0;
}
// 6
// 1 2
// 5 4
// 2 4
// 2 3
// 3 6