首页 > 代码库 > poj2378(树的dfs)
poj2378(树的dfs)
题目链接：http://poj.org/problem?id=2378
题意：给一个树状图，有n个点。求出，去掉哪个点，使得剩下的每个连通子图中点的数量不超过n/2。
分析：num[u]表示以u为根节点的子树的总节点树，判断下与u连接的儿子v代表的子树总节点num[v]和u的父亲代表的子树总节点n-num[u]即可。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010#define clr(a) (memset(a,0,sizeof(a)))using namespace std;struct edge{ int next,v; edge(){} edge(int v,int next):v(v),next(next){}}e[N*2];int head[N],tot,n,m;int num[N],vis[N];void addedge(int u,int v){ e[tot]=edge(v,head[u]); head[u]=tot++;}void dfs(int u,int fa){ bool flag=true; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(v==fa)continue; dfs(v,u); num[u]+=num[v]; if(num[v]>n/2)flag=false; } if(n-num[u]>n/2)flag=false; if(flag)vis[u]=1;}int main(){ int u,v; while(scanf("%d",&n)>0) { tot=0; memset(head,-1,sizeof(head));clr(vis); for(int i=1;i<=n;i++)num[i]=1; for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(1,-1); int flag=0; for(int i=1;i<=n;i++)if(vis[i])printf("%d\n",i),flag=1; if(!flag)puts("NONE"); }}
poj2378(树的dfs)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。