1 条题解

  • 0
    @ 2026-1-27 19:27:41
    #include<bits/stdc++.h>
    using namespace std;
    
    int n;               // [1] n-树的节点总数(编号1~n)
    int arr[110];        // [2] arr数组-存储每个节点的父节点(下标为节点编号,值为父节点编号)
    
    // 递归函数:查找节点c的根节点(根节点的父节点是自身)
    int f(int c){
        if(arr[c] == c) return c;  // [3] 如果当前节点c的父节点是自己,说明它就是根节点,直接返回
        else return f(arr[c]);     // [4] 否则递归向上查找父节点的根节点
    } 
    
    int main(){
        cin>>n;  // [5] 读取节点总数n
        // 初始化:假设每个节点的父节点是自己(根节点最终会满足arr[c]==c)
        for(int i=1;i<=n;i++) arr[i]=i;  // [6] 初始化父节点数组,每个节点初始父节点为自身
        
        // 读入n-1对父子关系,更新子节点的父节点
        int a,b;
        for(int i=1;i<n;i++){
            cin>>a>>b;
            arr[b]=a;  // [7] 输入X(a)是Y(b)的父节点,所以设置节点b的父节点为a
        }
        
        // 对每个节点,找到它的根节点(并更新arr[i]为根节点,实现路径压缩)
        for(int i=1;i<=n;i++){
            arr[i]=f(arr[i]);  // [8] 调用f函数找到节点i的根节点,并更新arr[i]为根节点
        }
        
        // 输出根节点(所有节点的根节点都相同,所以输出arr[1]即可)
        cout<<arr[1];  // [9] 输出树的根节点编号
        return 0;
    }
    
    • 1

    信息

    ID
    1065
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    1
    已通过
    1
    上传者