12178. 破坏牛棚割点割边

爱被打了一巴掌 2023-07-17 05:56 1阅读 0赞

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

输入格式:

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

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

输入:  
10  
1 2  
2 3  
3 4  
4 5  
6 7  
7 8  
8 9  
9 10  
3 8  
输出:  
3  
8  
说明:  
如果牛棚3或牛棚8被破坏，剩下的三个子网节点数将是5，2，2，没有超过5的。

#include <cstdio>
    #include <vector>
    
    //using namespace std;
    // 图论
    // 题意，给定一颗无根树，求满足要求的割点
    // 要求：去掉割点后产生的最大联通分量不多于n/2个节点
    const int N = 100002;
    
    int n,num[N],pre[N],root,ans=0;
    
    std::vector<int> g[N];
    
    int dfs(int cur,int father)
    {
        
    pre[cur]=father;
    if(cur!=root && g[cur].size()==1)
    {
        
    return num[cur]=1;
    }
    int sum=0,v;
    for(int i=0;i<g[cur].size();++i)
    {
        
    v=g[cur][i];
    if(v!=father)
    {
        
    sum+=dfs(v,cur);
    }
    }
    return num[cur]=sum+1;
    }
    
    int main()
    {
        
    scanf("%d",&n);
    int a,b;
    for(int i=1;i<n;++i)
    {
        
    scanf("%d %d",&a,&b);
    g[a].push_back(b);
    g[b].push_back(a);
    }
    // 选第一个节点为根节点
    root=1;
    // 深搜一遍，找出dfs序中，所有子树的节点个数
    dfs(1,0);
    // 遍历所有节点，找满足要求的割点
    for(int i=1;i<=n;++i)
    {
        
    // 如果去除这一子树i，剩余节点个数不满足要求，则跳过这一子树，继续寻找下一子树
    if(num[1]-num[i]>n/2)
    {
        
    continue;
    }
    // 遍历这一子树的所有子树
    bool p=true;
    for(int j=0;j<g[i].size();++j)
    {
        
    int v=g[i][j];
    // 跳过父节点
    if(v==pre[i])
    {
        
    continue;
    }
    if(num[v]>n/2)
    {
        
    p=false;
    break;
    }
    }
    if(p==true)
    {
        
    ++ans;
    printf("%d\n",i);
    }
    }
    if(ans==0)
    {
        
    printf("NONE");
    }
    
    return 0;
    }