12178. 破坏牛棚

约翰意识到贝茜建设网络花费了他巨额的经费，就把她解雇了。贝茜很愤怒，打算狠狠报复。她打算破坏刚建成的约翰的网络。约翰的网络是树形的，连接着N(1≤N≤10000)个牛棚，她打算切断某一个牛棚的电源，使和这个牛棚相连的所有电缆全部中断。之后，就会存在若干子网络。为保证破坏够大，每一个子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢？

输入格式:

第1行：一个整数N.
第2到N+1行：每行输入两个整数，表示一条电缆的两个端点．

输出格式:

按从小到大的顺序，输出所有值得破坏的牛棚．如果没有一个值得破坏，就输出NONE

样例 1 :

输出:
3
8

说明:
如果牛棚3或牛棚8被破坏，剩下的三个子网节点数将是5，2，2，没有超过5的。

 1 #include <cstdio>
 2 #include <vector>
 3 
 4 //using namespace std;
 5 // 图论
 6 // 题意，给定一颗无根树，求满足要求的割点
 7 // 要求：去掉割点后产生的最大联通分量不多于n/2个节点
 8 const int N = 100002;
 9 
10 int n,num[N],pre[N],root,ans=0;
11 
12 std::vector<int> g[N];
13 
14 int dfs(int cur,int father)
15 {
16 pre[cur]=father;
17 if(cur!=root && g[cur].size()==1)
18 {
19 return num[cur]=1;
20 }
21 int sum=0,v;
22 for(int i=0;i<g[cur].size();++i)
23 {
24 v=g[cur][i];
25 if(v!=father)
26 {
27 sum+=dfs(v,cur);
28 }
29 }
30 return num[cur]=sum+1;
31 }
32 
33 int main()
34 {
35 scanf("%d",&n);
36 int a,b;
37 for(int i=1;i<n;++i)
38 {
39 scanf("%d %d",&a,&b);
40 g[a].push_back(b);
41 g[b].push_back(a);
42 }
43 // 选第一个节点为根节点
44 root=1;
45 // 深搜一遍，找出dfs序中，所有子树的节点个数
46 dfs(1,0);
47 // 遍历所有节点，找满足要求的割点
48 for(int i=1;i<=n;++i)
49 {
50 // 如果去除这一子树i，剩余节点个数不满足要求，则跳过这一子树，继续寻找下一子树
51 if(num[1]-num[i]>n/2)
52 {
53 continue;
54 }
55 // 遍历这一子树的所有子树
56 bool p=true;
57 for(int j=0;j<g[i].size();++j)
58 {
59 int v=g[i][j];
60 // 跳过父节点
61 if(v==pre[i])
62 {
63 continue;
64 }
65 if(num[v]>n/2)
66 {
67 p=false;
68 break;
69 }
70 }
71 if(p==true)
72 {
73 ++ans;
74 printf("%d
",i);
75 }
76 }
77 if(ans==0)
78 {
79 printf("NONE");
80 }
81 
82 return 0;
83 }