【题目来源】
【题目描述】
一棵有 N 个结点的树，树上结点编号为 1 到 N。
已知树上 N-1 条边，且已知每条边的父子关系。
请编程求出树上根结点的编号。
【输入格式】
第 1 行输入一个整数 N 代表树上结点的数量。（1≤N≤100）。
接下来 N-1 行，每行输入两个整数 X，Y，代表编号为 X 的结点是编号为 Y 的结点的父。
【输出格式】
输出一个整数，代表树上根结点的编号。
【输入样例】
7
3 7
4 5
5 2
4 1
3 4
7 6
【输出样例】
3
【数据范围】
1≤N≤100
【算法分析】
找根的算法思想：遍历所有节点，直至父节点为空的节点，即为根。
【算法代码一：邻接表】
#include<bits/stdc++.h>
using namespace std;const int N=1e2+5;
vector<int> v[N];
int fa[N];
int n,x,y;int main() {memset(fa,-1,sizeof fa);cin>>n;for(int i=1; i<n; i++) {cin>>x>>y;fa[y]=x;v[x].push_back(y);}int root=x;while(fa[root]!=-1) {root=fa[root];}cout<<root<<endl;return 0;
}/*
in:
7
3 7
4 5
5 2
4 1
3 4
7 6out:
3
*/
【算法代码二：链式前向星】
#include<bits/stdc++.h>
using namespace std;const int N=1e2+5;
int e[N],ne[N],h[N],idx;
int fa[N];
int n,x,y;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int main() {memset(fa,-1,sizeof fa);memset(h,-1,sizeof h);cin>>n;for(int i=1; i<n; i++) {cin>>x>>y;fa[y]=x;add(x,y);}int root=x;while(fa[root]!=-1) {root=fa[root];}cout<<root<<endl;return 0;
}/*
in:
7
3 7
4 5
5 2
4 1
3 4
7 6out:
3
*/
【参考文献】