pat 甲级 1021 Deepest Root

发布时间:2024年01月24日

中文意思:

一个无环连通图可以被视作一个树。

树的高度取决于所选取的根节点。

现在,你要找到可以使得树的高度最大的根节点。

它被称为最深的根。

输入格式

第一行包含整数?N,表示节点数量。

节点编号为?1~N。

接下来?N?1?行,每行包含两个整数,表示两个节点之间存在一条边。

输出格式

输出最深的根的节点编号。

如果最深的根不唯一,则按照从小到大的顺序,将它们依次输出,每个占一行。

如果给定的图不是树,输出?Error: K components,其中?K是图中连通分量的数量。

----------------------------------------------------------------------------------------------------------------

解题思路:(1)首先是如何判断给定的图不是树。(2)如何判断最深的根的节点编号。

1.如何判断给定的图不是树,因为题目要输出图中连通分量的数量,我们可以想到用并查集的思想,即一开始每个节点都是一个连通分量,当节点有边时,合并成一个集合。这思想与pat的1013题相似,具体细节跳转链接(pat 甲级 1013 Battle Over Cities-CSDN博客)。

2.如何判断最深的根的节点。我们可以用邻接表来存储树,然后dfs递归遍历。这思想与pat的1004题相似,具体细节跳转(pat 甲级 1004 Counting Leaves-CSDN博客)。

整体代码如下:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=10010,M=N*2;
int p[N];//并查集使用的数组,表示i节点的祖宗节点
int n;
int h[N],e[M],ne[M];//邻接表存储树所需的数组
int idx;
int find(int x){//压缩路径,原理看查看上文的链接
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
void add(int a,int b){//邻接表存储边
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u,int father){//第一个变量表示从u开始dfs,第二个变量表示父节点,因为是无向图,标记 防止搜回父节点。
    int depth=0;
    for(int i=h[u];~i;i=ne[i]){//遍历邻接表
        int j=e[i];
        if(j==father) continue;
        depth=max(depth,dfs(j,u)+1);
    }
    return depth;
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);//邻接表的头节点全初始化为-1
    for(int i=1;i<=n;i++) p[i]=i;//并查集初始化
    int k=n;//n个节点,n个连通分量
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        int pa=find(a),pb=find(b);//查找祖宗节点
        if(pa!=pb){//不在同一个集合,有边则合并,连通分量-1
            p[pa]=pb;
            k--;
        }
        add(a,b);//添加边,无向图相当于a->b,b->a的有向图,添加两条边
        add(b,a);
    }
    if(k>1) printf("Error: %d components\n",k);
    else{
        vector<int> nodes;//存储最深的nodes
        int max_depth=-1;
        for(int i=1;i<=n;i++){
            int depth=dfs(i,-1);//第一个变量表示从i开始dfs,第二个变量表示父节点,因为是无向图,标记 防止搜回父节点。
            if(depth>max_depth){//有更深的结果
                nodes.clear();//清理所有的nodes
                nodes.push_back(i);//将最新的节点放入
                max_depth=depth;//更新depth
            }
            else if(depth==max_depth){
                nodes.push_back(i);
            }
        }
        for(auto v:nodes){
            cout<<v<<endl;
        }
    }
    return 0;
}

文章来源:https://blog.csdn.net/weixin_50671259/article/details/135768223
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。