题解 | 求树的根

/*
改进：这里的a[n - 1]和b[n - 1]可以不创建

设置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() {
    //读取数据n
    int n;
    scanf("%d\n", &n);
    
    //设置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++){
        int a, b;
        scanf("%d %d\n", &a, &b);
        in[b - 1] = 1;
        out[a - 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(in);
    free(out);
    return 0;
}