题解 | 求树的根

/*
设置a[n - 1]和b[n - 1]数组存储ai,bi
基本想法，设置in[n]和out[n]数组记录每个顶点是否有入度以及是否有出度,遍历a[n - 1]和b[n - 1]为in\out数组赋值，再扫描检测一遍in\out数组得出结果
*/


#include <stdio.h>
#include <stdlib.h>

int main() {
    //读取数据
    int n;
    scanf("%d\n", &n);
    int *a = (int *)malloc(sizeof(int) * (n - 1));
    int *b = (int *)malloc(sizeof(int) * (n - 1));
    for(int i = 0; i < n - 1; i++){
        scanf("%d %d\n", a + i, b + i);
    }
    
    //设置in\out数组并初始化
    int *in = (int *)malloc(sizeof(int) * n);
    int *out = (int *)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++){
        in[i] = 0;
        out[i] = 0;
    }
    
    //遍历a,b数组为in\out赋值
    for(int i = 0; i < n - 1; i++){
        in[b[i] - 1] = 1;
        out[a[i] - 1] = 1;
    }
    
    //扫描in\out数组，输出结果
    for(int i = 0; i < n; i++){
        if(in[i] == 0){
            printf("%d\n", i + 1);
            break;
        }
    }

    for(int i = 0; i < n; i++){
        if(out[i] == 0){
            printf("%d ", i + 1);
        }
    }
    
    printf("\n");
    //释放空间
    free(a);
    free(b);
    free(in);
    free(out);
    return 0;
}