题目描述

图的连通块的标记   二次bfs求树的直径端点  树的直径（树的最长链）
最深的树的根节点属于无线无环图的直径的端点

算法1

C++ 代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
const int N=1e4+10,M=2*N;
const int INF=0x3f3f3f;

int h[N],e[M],ne[M],w[M],idx;
int n;
int v[N],cnt=0;

int dist[N];
int vis[N];//标记节点是否访问

set<int> ans;

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void bfs(int s){
    memset(dist,INF,sizeof(dist));
    memset(vis,0,sizeof(vis));

    queue<int> q;
    q.push(s);
    dist[s]=0;vis[s]=1;


    while(q.size()){
        int t=q.front();q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(vis[j]){
                continue;
            }
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                vis[j]=1;
                q.push(j);
            }
        }
    }
}

void dfs(int x){
    v[x]=cnt;
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(v[j]){
            continue;
        }
        dfs(j);
    }
}

vector<int> find(){
    vector<int> res;
    int pos=1;
    for(int i=2;i<=n;i++){
        if(dist[pos]<dist[i]){
            res.clear();
            pos=i;
            res.push_back(i);
        }
        if(dist[pos]==dist[i]){
            res.push_back(i);
        }
    }
    return res;
}

int main(){
    cin>>n;
    memset(h,-1,sizeof(h));
    memset(v,0,size(v));

    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b,1);add(b,a,1);
    }

    //判断是否是联通的以及标号输出连通分量个数
    for(int i=1;i<=n;i++){
        if(!v[i]){
            cnt++;
            dfs(i);
        }   
    }
    int num=0;
    for(int i=1;i<=n;i++){
        if(v[i]>num){
            num=v[i];
        }
    }
    if(num!=1){
        cout<<"Error: "<<num<<" components"<<endl;
    }else if(num==1){//说明该图是联通的 无向无环图
        //求最深的根的编号,记录编号bfs求直径
        bfs(1);
        vector<int> pos1=find();//找到最远的节点，可能不止一个
        vector<int> pos2;

        // cout<<"pos1="<<pos1.size()<<"  "<<pos1[0]<<endl;

        for(int i=0;i<pos1.size();i++){
            ans.insert(pos1[i]);

            bfs(pos1[i]);
            pos2=find();

            // cout<<"pos2.size()"<<pos2.size()<<endl;
            for(int j=0;j<pos2.size();j++){
                ans.insert(pos2[j]);
            }
        }

        // cout<<"stine"<<ans.size()<<endl;
        for(auto it=ans.begin();it!=ans.end();it++){
            cout<<*it<<endl;
        }

    }

    return 0;
}