poj1523 解题报告

题意：给出一个无向图，要求找出每个割点，以及除去割点之后能把图分成几个连通块

题解：点的双联通，统计割点属于多少个连通块

代码：

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

const int MAXN = 1005 ;

struct type
{
    int  end , next ;
} ;

type  edge[MAXN*MAXN] ;
int   head[MAXN] , Count , top ;
int   low[MAXN] , dfn[MAXN] , stack[MAXN] , vis[MAXN] , ans[MAXN] ; // ans是每个点属于的集合的数量，大于1就是割点了

void  addedge( int start , int end )
{
    edge[Count].end  = end         ;
    edge[Count].next = head[start] ;
    head[start]      = Count ++    ;
}

void  tarjan_dfs( int cur , int father , int &cnt , int &Time )
{
    dfn[cur] = low[cur] = Time ++ ;
    vis[cur] = 1 ;
    for( int i = head[cur] ; i != -1 ; i = edge[i].next )
    {
        int  end = edge[i].end ;
        if( end == father ) continue ;
        if( !vis[end] )
        {
            tarjan_dfs( end , cur , cnt , Time )   ;
            low[cur] = min( low[cur] , low[end] )  ;
            if( dfn[cur] <= low[cur] ) ans[cur] ++ ; // dfn = low 也可以
        }
        else low[cur] = min( low[cur] , dfn[end] ) ;
    }
}

int  tarjan( int N )
{
    int  Time = 0 , cnt = 0 ;
    top = 0 ;
    memset( dfn , 0 , sizeof( dfn ) ) ;
    memset( low , 0 , sizeof( low ) ) ;
    memset( vis , 0 , sizeof( vis ) ) ;
    tarjan_dfs( 1 , -1 , cnt , Time ) ;
    return cnt ;
}

int  main()
{
    int  i , j , Max ;
    int  start , end , cnt ;

    memset( head , -1 , sizeof( head ) ) ;
    Count = 0 , cnt = 1 ;

    while( scanf( "%d" , & start ) && start )
    {
        memset( head , -1 , sizeof( head ) ) ;
        Count = 0 ;
        Max = 0 ;
        if( start > Max ) Max = start ;
        scanf( "%d" , & end ) ;
        if( end  > Max ) Max  = end  ;
        addedge( start , end ) ;
        addedge( end , start ) ;
        while( scanf( "%d" , & start ) && start )
        {
            if( start > Max ) Max = start ;
            scanf( "%d" , & end ) ;
            if( end  > Max )  Max = end ;
            addedge( start , end ) ;
            addedge( end , start ) ;
        }

        for( i = 2 ; i <= Max ; i ++ ) ans[i] = 1 ;
        ans[1] = 0 ;

        tarjan( Max ) ;

        printf( "Network #%d\n" , cnt ) ;
        int flag = 0 ;
        for( i = 1 ; i <= Max ; i ++ )
            if( ans[i] > 1 )
            {
                printf( "  SPF node %d leaves %d subnets\n" , i , ans[i] ) ;
                flag = 1 ;
            }
        if( !flag ) printf( "  No SPF nodes\n" ) ;
        printf( "\n" ) ;
        cnt ++ ;
    }
    return 0 ;
}