poj1144Network(无向图割点数)

题目大意：给一张无向图，求割点数量。

题目分析：tarjan算法求割点。关于无向图割点，这里说的很清楚了。直接建图跑一遍tarjan算法即可。

详情请见代码：

#include <iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 101;

int adj[N][N];

bool flag[N][N],vis[N];

int low[N],dfn[N],subnets[N];

int n,dfns;

char s[N];

void dfs(int cur)

{

    int i;

    vis[cur] = true;

    dfn[cur] = low[cur] = dfns ++;

    for(i = 1;i <= adj[cur][0];i ++)

    {

        if(vis[adj[cur][i]] == false)

        {

            dfs(adj[cur][i]);

            low[cur] = min(low[cur],low[adj[cur][i]]);

            if(low[adj[cur][i]] >= dfn[cur])

                subnets[cur] ++;

        }

        else

            low[cur] = min(low[cur],dfn[adj[cur][i]]);

    }

}

void tarjan()

{

    int i;

    memset(vis,false,sizeof(vis));

    memset(subnets,0,sizeof(subnets));

    dfns = 1;

    for(i = 1;i <= n;i ++)

        if(vis[i] == false)

        {

            subnets[i] --;

            dfs(i);

        }

    int ans = 0;

    for(i = 1;i <= n;i ++)

        if(subnets[i] > 0)

            ans ++;

    printf("%d\n",ans);

}

int main()

{

    int i,j,p;

    freopen("in.txt","r",stdin);

    while(scanf("%d",&n),n)

    {

        memset(flag,false,sizeof(flag));

        memset(adj,0,sizeof(adj));

        while(scanf("%d",&i),i)

        {

            gets(s);

            p = 0;

            while(s[p] && s[p] == ' ')

                p ++;

            while(sscanf(s + p,"%d",&j) == 1)

            {

                if(flag[i][j] == false)

                {

                    flag[i][j] = flag[j][i] = true;

                    adj[i][++ adj[i][0]] = j;

                    adj[j][++ adj[j][0]] = i;

                }

                while(s[p] && s[p] != ' ')

                    p ++;

                while(s[p] && s[p] == ' ')

                    p ++;

            }

        }

        tarjan();

    }

    return 0;

}

//188K	16MS

巴特西

poj1144Network(无向图割点数)

最新文章

热门文章