无向图的割顶（poj1523，1144）

偏执的太偏执、 2022-08-08 11:55 112阅读 0赞

割顶：表示无向图中的点，这个点删除之后，原图不在联通，这样的点就是割顶。  
怎么求一个图中的割顶呢？  
把无向图变成一颗树，dfs时候搜索到在dfs树上的称为树边，搜索是出现后代指向祖先的边称为反向边。  
对于根节点，当他存在两个或两个以上的子节点时，那么他就是割顶。  
而对于其他节点u，当且仅当u存在一个子节点v，使得v及其所有的后代都没有反向边连回u的祖先时，u是一个割顶。  
那么判断就很简单，这里给出两个模板：  
题目：poj1523 和 1144都是裸的求割顶的题目  
通用模板：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    using namespace std;
    
    const int N=1100;
    
    int dfn[N],low[N],vis[N],cnt[N];
    ///dfn 表示深搜的时候的标号   low表示他能连到最早的点
    bool cut[N];
    int k,n,root;
    vector<int> g[N];
    
    void addedge(int x,int y){
        g[x].push_back(y);
        g[y].push_back(x);
    }
    void Tarjan(int u,int fa)
    {
        int son = 0;
        vis[u] = 1;
        dfn[u] = low[u] = ++k;
        for(int i=0;i<g[u].size();i++)
        {
            int v = g[u][i];
            if(vis[v]==1 && v!=fa)
                low[u] = min(low[u],dfn[v]);
            if(vis[v]==0)
            {
                Tarjan(v,u);
                son++;
                low[u] = min(low[u],low[v]);
                if((u==root && son>1) || ( u!=root && low[v]>=dfn[u] ) )
                    cut[u]= 1,cnt[u]++;
            }
        }
        vis[u] = 2;
    }
    int main()
    {
    //    freopen("Input.txt","r",stdin);
        int cas = 1;
        while(true)
        {
            int x,y,n = 0;
            scanf("%d",&x);
            if(x==0)
                break;
            scanf("%d",&y);
            addedge(x,y);
            n = max(n,x),n = max(n,y);
            while(~scanf("%d",&x) && x)
            {
                scanf("%d",&y);
                n = max(n,x);
                n = max(n,y);
                addedge(x,y);
            }
            k = 0;
            memset(dfn,0,sizeof(dfn));
            memset(low,0,sizeof(low));
            memset(vis,0,sizeof(vis));
            memset(cut,0,sizeof(cut));
            memset(cnt,0,sizeof(cnt));
            root = 1;
            cnt[root] = 0;  ///注意初始点会多算一次，因为它本身会把它的子节点都计算出来
            Tarjan(root,-1);
            int ans = 0;
            for(int i=1;i<=n;i++)
                if(cut[i])
                    ans++;
            printf("Network #%d\n",cas++);
            if(ans==0)
                puts("  No SPF nodes");
            else
            {
                for(int i=1;i<=n;i++)
                {
                    if(cut[i])
                        printf("  SPF node %d leaves %d subnets\n",i,cnt[i]+1);
                }
            }
            puts("");
            for(int i=0;i<=n;i++)
                g[i].clear();
        }
        return 0;
    }

还有一个大白书上的模板，写法差不多，但是提交到1144上wa了

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <math.h>
    #include <vector>
    #include <cstring>
    #include <cstdio>
    #include <stack>
    #include <map>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 1100;
    const int inf = 0x3f3f3f3f;
    vector<int> v[N];
    int dfs_clock;
    int pre[N],cnt[N];
    bool iscut[N];
    int dfs(int now,int fa)
    {
        int lownow = pre[now] = ++dfs_clock;
        int child = 0;
        for(int i=0;i<v[now].size();i++)
        {
            int to = v[now][i];
            if(pre[to]==0)
            {
                child++;
                int lowto = dfs(to,now);
                lownow = min(lowto,lownow);
                if(lowto >= pre[now])  ///here isn't equer?
                {
                    iscut[now] = true;
                    cnt[now]++;
                }
            }
            else if(pre[to] < pre[now] && to!=fa)  ///erevy update
                lownow = min(lownow,pre[to]);
        }
        if(fa<0 && child==1)
            iscut[now] = false;
        ///low[u] = lownow;  if want
        return lownow;
    }
    
    int main()
    {
    //    freopen("Input.txt","r",stdin);
        int cas = 1;
        while(true)
        {
            int x,y,n = 0;
            scanf("%d",&x);
            if(x==0)
                break;
            scanf("%d",&y);
            v[x].push_back(y);v[y].push_back(x);
            n = max(n,x),n = max(n,y);
            while(~scanf("%d",&x) && x)
            {
                scanf("%d",&y);
                n = max(n,x);
                n = max(n,y);
                v[x].push_back(y);
                v[y].push_back(x);
            }
            dfs_clock = 0;
            for(int i=0;i<=n;i++)
            {
                pre[i] = 0;
                cnt[i] = 1;
                iscut[i] = false;
            }
            cnt[1] = 0;  ///注意初始点会多算一次，因为它本身会把它的子节点都计算出来
            dfs(1,-1);
            int ans = 0;
            for(int i=1;i<=n;i++)
                if(iscut[i])
                    ans++;
            printf("Network #%d\n",cas++);
            if(ans==0)
                puts("  No SPF nodes");
            else
            {
                for(int i=1;i<=n;i++)
                {
                    if(iscut[i])
                        printf("  SPF node %d leaves %d subnets\n",i,cnt[i]);
                }
            }
            puts("");
            for(int i=0;i<=n;i++)
                v[i].clear();
        }
        return 0;
    }