题解 | 求树的根

vector结合pair形式

用vector结合pair直接统计每个节点的出度和入度 (指向其他节点次数和被其他节点指向次数)

出度为0的为叶 入度为1的为根(只输出第一个）

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a;
    cin>>a;
    int aa=a-1;
    vector<pair<int,int>> cc(a+1,{0,0});//出度，入度
    while(aa--){
        int b,c;
        cin>>b>>c;
        cc[b].first++;//出度(指向个数)
        cc[c].second++;//入度(被指向个数)
    }
    vector<int> dd;//叶
    int cnt=0;
    for(int i=1;i<a+1;i++){
        if(cc[i].first==0){
            dd.push_back(i);
        }
        if(cc[i].second==0 && cnt == 0){
            cout<<i<<'\n';
            cnt++;
        }
    }
    sort(dd.begin(),dd.end());
    int ds=dd.size();
    for(int i=0;i<ds;i++){
        cout<<dd[i]<<" ";
    }
}

二维map形式

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a;
    cin >> a;
    int aa = a - 1;
    map<int, map<string, int>> cc; //编号 出度 入度
    // 初始化出度、入度为0
    for (int i = 1; i <= a; ++i) {
        cc[i]["out"] = 0; //出度
        cc[i]["in"] = 0;  //入度
    }
    while (aa--) {
        int b, c;
        cin >> b >> c;
        cc[b]["out"]++;  
        cc[c]["in"]++;  
    }
    vector<int> dd; //叶
    int cnt = 0;   
    // 遍历外层map
    for (auto& i : cc) { 
        if ( i.second["out"] == 0) {           
            dd.push_back(i.first);
        }
        if (i.second["in"] == 0 && cnt == 0) {
            cout << i.first << '\n';
            cnt++;
        }
    }

    // 叶
    sort(dd.begin(), dd.end());
    int ds = dd.size();
    for (int i = 0; i < ds; ++i) {
        cout << dd[i] << " ";
    }

    return 0;
}

速度优化(2ms)

用静态数组代替STL，用scanf和printf代替cin和cout，去掉sort ，cstdio换成stdio.h

#include <stdio.h>
const int MAX = 1e5 + 1;
int ot[MAX]={0},in[MAX]={0}, dd[MAX]; // 出度 入度 叶
int main() {
    int a;
    scanf("%d", &a); 
    int aa = a - 1;
    for (int i = 0; i < aa; ++i) {
        int b, c;
        scanf("%d%d", &b, &c);
        ot[b]++;  
        in[c]++; 
    }
    int d=-1,ddd = 0;
    for (int j = 1; j <= a; ++j) {
        if (in[j] == 0 && d == -1) {
            d = j;
            printf("%d\n", d); 
        }
        if (ot[j] == 0) {
            dd[ddd++] = j;
        }
    }
    for (int k = 0; k < ddd; ++k) {
        printf("%d ", dd[k]);
    }
    return 0;
}