题解 | 求树的根

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

const int N=1e5+10;

int n,in[N],out[N];

void add(int u,int v){
	edge[++cnt].next=head[u];
	edge[cnt].u=u;
	edge[cnt].v=v;
	head[u]=cnt;
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n;
	int u,v;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v;
		out[u]++;in[v]++;
	}
	vector<int> v_child;
	int father=-1;
	for(int i=1;i<=n;i++){
		if(out[i]==0) v_child.push_back(i);
		if(in[i]==0&&father==-1) father=i;
	}
	sort(v_child.begin(),v_child.end());
	cout<<father<<endl;
	for(int i=0;i<v_child.size();i++){
		cout<<v_child[i]<<" ";
	}
	cout<<endl;
    return 0;
}