PAT 1021

题目 ： Deepest Root

分值 ： 25
难度 ： 中等题
思路 ： 路径压缩先判断连统集，然后用一个佛洛依德算法搞出点到点的最短路径，找到最大的就是
       最深的根，然后就是把最大的涉及的头和尾记录下来，顺序打印即可。
坑点 ： 这里因为只有N-1 条边，是个稀疏图，因此使用二维数组存图内存超限，要邻接表，不习惯
评语 ： 很综合的题目，路径压缩判断联通集合数，然后佛洛依德一下，关键是要邻接表实现才能全
       部ac让人很生气，邻接表不想去做。
第二次复习时的做法：(因为我的做法内存使用弗洛伊德内存超限,因此参考了柳诺大神的DFS思路)
       使用DFS 判断有几个联通集,从 1到 N号节点,如果当前节点未被访问过就对他
       DFS,并且cnt++ ; 直到所有的节点都被访问过,然后看 cnt是否为一 ;因为如果cnt为1,也
       就说明第一次从1这个节点往下深搜,其他所有节点都被访问到,也就是所有点在同一联通集.
       关于最深的节点集合: 第一次深搜得到的最深的节点们 记录在 set s 中,然后任意取其中一
       个节点,对其DFS(要记得初始条件清零),也就等同于从边缘的点开始深搜整棵树树,然后得到的
       节点继续记录在 set s中,这两次DFS的并集就是答案,且set是自动升序排序的.
感觉 ： 感觉自己的DFS要强化,包括普通 DFS 和 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
#include <iostream>
#include <set>
#include <vector>
using namespace std;
vector < vector<int> > Map;
vector <int> temp ;
bool flag[10010] ;
set<int > s ;
int max_height = 0 ;
void Dfs(int x , int deep)
{
    flag[x] = true ;
    if(deep > max_height)
    {
        temp.clear();
        max_height = deep ;
        temp.push_back(x) ;
    }else if(deep == max_height)
        temp.push_back(x) ;
    for(int i = 0 ; i< Map[x].size() ; i++)
    {
        if(flag[Map[x][i]] == false )
            Dfs(Map[x][i] , deep+1) ;
    }
}
int main()
{
    int N ,c1,c2,s1,cnt=0 ;
    cin >> N ;
    Map.resize(N+1) ;
    for(int i = 0 ; i< N-1 ; i++)
    {
        cin >>c1 >>c2 ;
        Map[c1].push_back(c2) ;
        Map[c2].push_back(c1) ;
    }
    for(int i =1 ; i<=N ; i++)
    {
        if(flag[i] ) continue ;
        Dfs(i , 1 ) ;
        if(i ==1 )
        {
            if(temp.size()!=0 ) s1 = temp[0] ;
            for(int j = 0 ;j< temp.size(); j++)
                s.insert(temp[j]) ;
        }
        cnt++;
    }
    if(cnt >=2 )
        printf("Error: %d components\n" , cnt) ;
    else
    {
        max_height = 0 ;
        temp.clear();
        fill(flag, flag+10010 , false );
        Dfs(s1,1) ;
        for(int i = 0 ; i< temp.size() ; i++)
            s.insert(temp[i]) ;
        for(auto i = s.begin() ; i!=s.end() ; i++)
            cout << *i<<endl ;
    }
}