1 条题解

  • 2
    @ 2022-12-29 20:01:55

    详见注释:

    #include <bits/stdc++.h>
    using namespace std;
    int n , x , y , t[1005] , s[1005] , maxxn , maxx;
    /*
    t保存每个节点的父节点
    s保存每个节点的子节点数量
    maxxn保存子节点最多的结点编号
    maxx保存子节点最多的结点的子节点数量(真绕)
    f保存此节点是否出现过
    */
    bool f[1005];
    int main()
    {
        memset(f , false , sizeof(f));//初始化
        scanf("%d" , &n);
        for (int i = 1 ; i < n ; i++)//看似题目中说输入若干行x和y,实则必定有n-1条数据,因为一个有n个顶点的树必定有n-1条边
        {
            scanf("%d %d" , &x , &y);
            t[y] = x;//将y的父节点存入数组t
            //编号为x和y的顶点已出现过
            f[x] = true;
            f[y] = true;
            //顶点x的子节点数量+1
            s[x]++;
        }
        //找根节点
        for (int i = 1 ; i <= 1000 ; i++)
        {
            if (t[i] == 0 && f[i])//i的父亲为0(既没有父亲)而且出现过,只有根节点满足此条件
            {
                printf("%d\n" , i);
                break;//退出循环
            }
        }
        //找子节点最多的结点
        for (int i = 1 ; i <= 1000 ; i++)
        {
            if (s[i] >= maxx)
            {
                maxx = s[i];
                maxxn = i;
            }
        }
        printf("%d\n" , maxxn);
        //找到子节点最多的结点的所有子节点
        for (int i = 1 ; i <= n ; i++)
        {
            if (t[i] == maxxn)
                printf("%d " , i);
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1184
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    28
    已通过
    18
    上传者