wustoj(寻找根节点和孩子)

今天药忘吃喽~ 2022-06-05 05:38 112阅读 0赞

问题描述:

给定一棵树（结点数大于1小于1000），输出树的根root，孩子最多的结点以及他的孩子。如果存在多个答案，请输出所有的答案。

Input

包含多组测试数据。每组测试数据第一行包括1个整数n（结点数，编号从1到n）。接下来n-1行，每行2个整数x y，表示结点y是结点x的孩子。

Output

第一行输出树根root和孩子最多的结点数max。

第二行输出孩子最多的结点以及其孩子。如果有多个结点，换行输出。

所有输出整数之间用空格隔开。

sample input

8  
4 1  
4 2  
1 3  
1 5  
2 6  
2 7  
2 8  
7  
1 2  
1 3  
3 4  
3 5  
5 6  
5 7

sample output

4 3

2 6 7 8

1 2

1 2 3

3 4 5

5 6 7

题目分析:我们可以选择用并查集来找根节点，在输入的时候我们可以把每个节点的儿子节点和其个数保存起来，寻找最多的儿子节点

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    const int maxn=1000;
    vector<int> vec[maxn];
    int pre[maxn+100],ans[maxn+100],n;
    void init()
    {
        for (int i=1;i<=n;i++)
            pre[i]=i;
    }
    int find(int x)
    {
        int r=x;
        while (pre[r]!=r)
            r=pre[r];
        int cur=x;
        while (cur!=r) {
            int res=pre[cur];
            pre[cur]=r;
            cur=res;
        }
        return r;
    }
    void join(int x,int y)
    {
        int fx=find(x);
        int fy=find(y);
        if (fx!=fy)
            pre[fy]=fx;
    }
    
    int main()
    {
        while (scanf("%d",&n)!=EOF) {
            init();
            memset (ans,0,sizeof (ans));
            for (int i=1;i<=n-1;i++) {
                int a,b;
                scanf("%d%d",&a,&b);
                ans[a]++;
                vec[a].push_back(b);
                join(a,b);
            }
            for (int i=1;i<=n;i++)//这里还要用一次，因为有的点没有连起来
                join(pre[i],i);
            int Max=0;
            for (int i=1;i<=n;i++)
                Max=max(Max,ans[i]);
            printf("%d %d\n",find(1),Max);
            for (int i=1;i<=n;i++) {
                if (ans[i]==Max) {
                    printf("%d ",i);
                    for (int j=0;j<Max;j++) {
                        if (j==Max-1) printf("%d\n",vec[i][j]);
                        else printf("%d ",vec[i][j]);
                    }
                }
            }
            for (int i=1;i<=n;i++)
                vec[i].clear();
        }
        return 0;
    }