首页 > 其他 > 详细

poj2378

时间:2019-06-09 10:01:04      阅读:116      评论:0      收藏:0      [点我收藏+]

 

 

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1e4+10;
vector<int> e[maxn];
int vis[maxn];
int ans[maxn],cnt;
int v[maxn];
int n;
int dfs(int x)
{
    v[x]=1;
    int sum=1;
    int childmax=0;
    for(int i=0; i<e[x].size(); i++)
    {
        int y=e[x][i];
        if(v[y]==1) continue;
        int dian=dfs(y);
        sum+=dian;
        childmax=max(childmax,dian);
    }
    if(childmax<=n/2&&(n-sum)<=n/2)
        ans[++cnt]=x;
    return sum;
}
int main()
{

    scanf("%d",&n);
    for(int i=1; i<=n-1; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        e[a].push_back(b);
        e[b].push_back(a);
        vis[b]=1;
    }
    int root;
    for(int i=1; i<=n; i++)
    {
        if(vis[i]==0)
        {
            root=i;
            break;
        }
    }
//    printf("root=%d\n",root);
    dfs(root);
    sort(ans+1,ans+1+cnt);
    for(int i=1; i<=cnt; i++)
    {
        if(i!=cnt) printf("%d\n",ans[i]);
        else printf("%d",ans[i]);
    }
}

 

poj2378

原文:https://www.cnblogs.com/dongdong25800/p/10992586.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!