【题解-信息学奥赛一本通】1336：【例3-1】找树根和孩子
题目：1336：【例3-1】找树根和孩子
题目描述
给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子。
输入
第一行：n（结点个数≤100），m（边数≤200）。
以下m行：每行两个结点x和y，表示y是x的孩子(x,y≤1000)。
输出
第一行：树根：root；
第二行：孩子最多的结点max；
第三行：max的孩子（按编号由小到大输出）。
时空限制
1s / 64MB
样例输入
8 7 4 1 4 2 1 3 1 5 2 6 2 7 2 8样例输出
4 2 6 7 8代码
#include<bits/stdc++.h>usingnamespacestd;constintN=1000+10;intn,m,x,y,fa[N],minn=1e9,maxx,j,sonj;boolst[N];vector<int>g[N];intmain(){cin>>n>>m;while(m--){cin>>x>>y;g[x].push_back(y);st[x]=st[y]=true;fa[y]=x;minn=min(minn,min(x,y));maxx=max(maxx,max(x,y));}for(inti=minn;i<=maxx;i++){if(!fa[i]&&st[i])cout<<i<<endl;}for(inti=minn;i<=maxx;i++)if(g[i].size()>sonj){sonj=g[i].size();j=i;}cout<<j<<endl;sort(g[j].begin(),g[j].end());for(inti=0;i<g[j].size();i++)cout<<g[j][i]<<" ";return0;}