poj1523 解題報告

題意：給出一個無向圖，要求找出每個割點，以及除去割點之後能把圖分成幾個連通塊

題解：點的雙聯通，統計割點屬於多少個連通塊

代碼：

[cpp]
#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 ;