算法基础之树的重心

2023-12-13 21:21:06

树的重心

  • 无向图: 边没有方向 有向图:边有方向 只能单向询问

    • 无向图建立双向的边

    • 要求输出每种情况连通块个数最大值的最小值**(最小的最大值)**

    • 在这里插入图片描述

    •   #include <cstdio>
        #include <cstring>
        #include <iostream>
        #include <algorithm>
        using namespace std;
        
        const int N=100010, M=N*2;
        
        int n;
        //类似拉链法 的存储方式
        int h[N], e[M], ne[M], idx;  
        //h[N]为n条以1~n为头节点的单链表  
        //e[N]为节点数值(编号)
        //ne[N]为指针
        int ans = N;  //ans为最终结果 因为要取最小的最大值 所以ans初始为最大值
        bool st[N];  //判断是否遍历过 
        
        void add(int a, int b)
        {
            e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
            //拉链法
        }
        
        int dfs(int u)
        {
            st[u] = true;  //标记遍历过 防止下一层时往回递归 死循环
            
            int size=0,sum=1;  //初始化 最大子树大小size 当前节点为根节点的整棵树大小sum
            for(int i=h[u];i!=-1;i = ne[i])
            {
                int j = e[i];
                if(st[j]) continue;  //j如果没被遍历过 才执行
                int s = dfs(j);  //递归找子树大小
                sum+=s;  //求所有子树大小和 再向上返回
                size = max(s,size);  //找最大子树大小
            }
             
            size = max(size, n - sum);  //因为从整棵树的根节点开始遍历 当前节点向上一定为一整个连通块 有了下面的最大子树大小 再求上面的连通块大小比较
            ans = min(ans,size);
            
            return sum;
        }
        
        int main(){
            cin>>n;
            
            memset(h, -1, sizeof h);  //初始化
            
            for (int i = 0; i < n - 1; i ++ ){
                int a,b;
                cin>>a>>b;
                add(a,b),add(b,a);  //建立双向边
            }
            
            dfs(1);  //从根节点开始
            
            cout<<ans<<endl;
            
            return 0;
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/134980791
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。