1021. Deepest Root (25)—

1021. Deepest Root (25)——DFS+并查集

http://pat.zju.edu.cn/contests/pat-a-practise/1021

无环连通图也可以视为一棵树，选定图中任意一点作为根，如果这时候整个树的深度最大，则称其为 deepest root。给定一个图，按升序输出所有 deepest root。如果给定的图有多个连通分量，则输出连通分量的数量。

1.使用并查集判断图是否为连通的。

2.任意选取一点，做 dfs 搜索，选取其中一个最远距离的点 A，再做一次 dfs，找到的所有距离最远的点以及点 A 都是 deepest root。

考虑到为稀疏图，则使用动态链表

#include<stdio.h>
#include<stack>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std;

vector<int> map[10099]; 
int f[10099];
int find(int k){
    if(f[k]==-1)return k;
    else
        return f[k]=find(f[k]);
}

int um(int a,int b){
    int fa,fb;
    fa=find(a);
    fb=find(b);

    if(fa==fb)return 0;//表示有环

    if(fa!=fb)
        f[fa]=fb;
    return 1;
}

int step[10099];

void dfs(int x,int STEP){
    
    int i;
    for(i=0;i<map[x].size();i++){
        if(step[map[x][i]]!=0)continue;
        step[map[x][i]]=STEP;
        dfs(map[x][i],STEP+1);
    }
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        int i,a,b;
        
        for(i=0;i<=n;i++){
            f[i]=-1;
            step[i]=0;
        }

        int huan=0;
        for(i=1;i<n;i++){
            scanf("%d%d",&a,&b);
            if(um(a,b)==0)huan=1;

            map[a].push_back(b);
            map[b].push_back(a);
        }
        int connectAdd=0;
        set<int>set1;
        int ttemp;
        for(i=1;i<=n;i++){
            ttemp=find(i);
            set1.insert(ttemp);
        }

        if(set1.size()>=2||huan==1){
            printf("Error: %d components
",set1.size());continue;
        }
        step[1]=1;
        dfs(1,2);

        int max=0,ri;
        for(i=1;i<=n;i++){
            if(max<step[i]){
                max=step[i];
                ri=i;
            }
        }

        for(i=1;i<=n;i++){
            step[i]=0;
        }
        step[ri]=1;
        dfs(ri,2);

        max=0;
        for(i=1;i<=n;i++){
            if(max<step[i]){
                max=step[i];
            }
        }

        for(i=1;i<=n;i++){
            if(step[i]==max||step[i]==1){
                printf("%d
",i);
            }
        }
    }
    
    return 0;
}

View Code

其实上面的算法还有点问题，虽然AC了

考虑

5
1 2
1 3
2 4
2 5

应该是输出

算法改进以（第2次dfs最深的点）为起点,再做DFS得到的最深的点，这些点才是所有最深的点

#include<stdio.h>
#include<stack>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std;

vector<int> map[10099]; 
int f[10099];
int find(int k){
    if(f[k]==-1)return k;
    else
        return f[k]=find(f[k]);
}

int um(int a,int b){
    int fa,fb;
    fa=find(a);
    fb=find(b);

    if(fa==fb)return 0;//表示有环

    if(fa!=fb)
        f[fa]=fb;
    return 1;
}

int step[10099];
int deepF[10099];//第2次dfs最深的点
int deepR[10099];//以（第2次dfs最深的点）为起点,做DFS得到的最深的点

void dfs(int x,int STEP){
    
    int i;
    for(i=0;i<map[x].size();i++){
        if(step[map[x][i]]!=0)continue;
        step[map[x][i]]=STEP;
        dfs(map[x][i],STEP+1);
    }
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        int i,a,b,j;
        
        for(i=0;i<=n;i++){
            f[i]=-1;
            step[i]=0;
            deepF[i]=0;
            deepR[i]=0;
        }

        int huan=0;
        for(i=1;i<n;i++){
            scanf("%d%d",&a,&b);
            if(um(a,b)==0)huan=1;

            map[a].push_back(b);
            map[b].push_back(a);
        }
        int connectAdd=0;
        set<int>set1;
        int ttemp;
        for(i=1;i<=n;i++){
            ttemp=find(i);
            set1.insert(ttemp);
        }

        if(set1.size()>=2||huan==1){
            printf("Error: %d components
",set1.size());continue;
        }
        step[1]=1;
        dfs(1,2);

        int max=0,ri;
        for(i=1;i<=n;i++){
            if(max<step[i]){
                max=step[i];
                ri=i;
            }
        }

        for(i=1;i<=n;i++){
            step[i]=0;
        }
        step[ri]=1;
        dfs(ri,2);

        max=0;
        for(i=1;i<=n;i++){
            if(max<step[i]){
                max=step[i];
            }
        }

        for(i=1;i<=n;i++){
            if(step[i]==max||step[i]==1){
                //printf("%d
",i);
                deepF[i]=1;
                deepR[i]=1;
            }
        }

        for(i=1;i<=n;i++){
            if(deepF[i]==0)continue;
            for(j=1;j<=n;j++)step[j]=0;

            dfs(i,2);
            for(j=1;j<=n;j++){
                if(step[j]==max)deepR[j]=1;
            }
        }

        for(i=1;i<=n;i++){
            if(deepR[i]==1)printf("%d
",i);
        }
    }
    
    return 0;
}

View Code