首页 > 代码库 > Poj 1144 Zoj 1311 求割点 模板

Poj 1144 Zoj 1311 求割点 模板

2024-07-12 16:09:26   220人阅读

写这个就是为了手写一份好用的求割点模板：
吐槽下，题目中的 Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place.  这个at most是不可信的，应该是用大于n行的测试数据，因为这个我WA了。。。


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;


const int MAXN = 100+10;


int mat[MAXN][MAXN],son,subset[MAXN],dfn[MAXN],low[MAXN],vis[MAXN],tmpdfn;
//son,subset记录连通分量个数，
//如果是根节点，son==把根节点去掉后的连通分支个数，
//如果不是根节点，subset[i]+1==把该节点去掉后的连通分支个数
//所以根节点和其他节点区分开了
int n;


void init()
{
    son=tmpdfn=0;
    memset(vis,0,sizeof(vis));
    memset(mat,0,sizeof(mat));
    memset(subset,0,sizeof(subset));
    memset(dfn,0,sizeof(dfn));
    int u,v;
    char ch;
    while (scanf("%d",&u),u)
    {
        while(getchar()!=‘\n‘)
        {
            scanf("%d",&v);
            mat[u][v]=mat[v][u]=1;
        }
    }
}


void dfs(int u)
{
    dfn[u]=low[u]=tmpdfn++;
    for(int i=1;i<=n;i++)
    {
        if(mat[u][i])
            if(!vis[i])
            {
                vis[i]=1;
                dfs(i);
                low[u]=min(low[u],low[i]);
                if(low[i]>=dfn[u])//关节点的第二个条件
                {
                    if(1 == u)son++;
                    else subset[u]++;
                }
            }
            else
                low[u]=min(low[u],dfn[i]);
                //low[u]=Min{dfn[u],Min{low[w]|w是u的一个子女},Min{dfn[v]|v与u邻接,且(u,v)是一条回边}}
                //此处就是回边的情况，所以是dfn[i]而不是low[i],!!!注意low的定义
    }
}


int solve()
{
    init();
    for(int i=1;i<=n;i++)//可能本身不是连通图
        if(!vis[i])
        {
            vis[i]=1;
            dfs(i);
            if(son)
            {
                subset[i]=son-1;
                son=0;
            }
        }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(subset[i])ans++;//subset[i]+1就是去掉割点后所形成的连通分支个数
    }
    return ans;
}


int main()
{
    //freopen("poj1144.txt","r",stdin);
    while(~scanf("%d",&n) && n)
    {
        printf("%d\n",solve());
    }
    return 0;
}
































        

            
                
                  
                
                

                    联系

                    我们