3608 - 找树根和孩子

8 7
4 1
4 2
1 3
1 5
2 6
2 7
2 8

4
2
6 7 8

提示

	注意:孩子最多的不一定是一个结点。如果是多个结点都应该输出。


	例如：


	输入


	7 6
1 2

1 3

3 4

3 5

5 6

5 7


输出<br />

1

1

2 3

3

4 5

5

6 7

C++解答

#include<iostream>
#include<set>
using namespace std;
int main(){
    int n,m;    cin>>n>>m;
    int father[n+1];  //存父亲下标的数组   双亲表示法
    set<int> CH[n+1]; //为每个节点开一个set   存储它的孩子
	for(int i=1;i<=n;i++) father[i]=-1;
	int x,y;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y;
		father[y]=x;
		CH[x].insert(y);
	}
	for(int i=1;i<=n;i++)
		if(father[i]==-1) cout<<i<<endl;
    int max=0;
	for(int i=1;i<=n;i++)   //扫描一次，统计最大值
        if(CH[i].size()>max) max=CH[i].size();

    for(int i=1;i<=n;i++)
    if(CH[i].size()==max){
        cout<<i<<endl;
        set<int>::iterator it;
        for(it=CH[i].begin();it!=CH[i].end();it++)
            cout<<*it<<' ';
        cout<<endl;
    }
	    //cout<<i<<':'<<CH[i].size()<<endl;
    return 0;
}