题目描述

一个电话线公司（简称 TLC）正在建立一个新的电话线缆网络。

他们连接了若干个地点，编号分别从 1 到 N，没有两个地点有相同的号码，这些线是双向的并且能使两个地点保持通讯，每个地点的线都终结于电话交换机。

每个地点都有一个电话交换机。

从每个地点都能通过线缆到达其他任意的地点，然而它并不需要直接连接，它可以通过若干个交换机来到达目的地。

有时候某个地点供电出问题时，交换机就会停止工作。

TLC 的工作人员意识到，除非这个地点是不可达的，否则这种情况就会发生，它还会导致一些其它的地点不能互相通讯。

在这种情况下我们会称这个地点（错误发生的地方）为灾区。

现在工作人员想要写一个程序统计所有灾区的数量。

输入格式

输入文件包括若干组测试数据。

每组数据描述一个网络，第一行是地点的总数量 N。

接下来若干行（最多 N 行），每行包含若干数字，第一个数字表示一个地点的编号，后面的数字表示与该地点相连接的地点的编号。

一行内的所有数字都要用空格隔开。

每组数据输入完毕后，都需要用单独的一个 0 结束。

当输入 N=0 时，表示输入结束。

输出格式

每组数据输出一个答案，占一行，表示灾区的数量。

解题关键：

割点判定法则
    1. 当x 不是搜索树的根节点： x是割点当且仅当搜索树存在一子节点y，满足 dfn[x] <= low[y].
    2. 当x 是根节点： x 是割点当且仅当搜索树存在两个子节点y1，y2 满足上式.

文献参考

《算法竞赛进阶指南》 P398

tips

此题的输出需特别注意，有点不同以往。
边的数组需要开大一点，否则会超时。
特别的，此题是一个连通块，事实上只需要tarjan(1)即可。不需要对每一个结点进行tarjan。

C++ 代码

#pragma GCC optimize(3)
#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std ;

const int N= 110, M = 1000;
int n , m; 
int h[N],e[M],ne[M] , idx ;
int dfn[N] ,low[N],ts ;
int child , ans ;
int root ;
bool iscut[N] ;

void add(int a, int b) 
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ; 
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ ts ;
    for(int i = h[u];~i ; i = ne[i] )
    {
        int j = e[i] ;
        if(!dfn[j]) 
        {
            tarjan(j) ;
            low[u] = min(low[u] , low[j] ) ;  // 对回溯和时间戳的维护
            if(low[j] >= dfn[u] && u != root )  // 对非根节点的割点的判定
            {
                iscut[u] = 1 ;
            }
            else if(u == root && low[j] >= dfn[u] ) // 对根节点的割点的判定
            {
                child ++ ;  // 满足条件的子节点child ++ 
            }
        }
        else 
        {
            low[u] = min(low[u] , dfn[j]) ;  // 对回溯和时间戳的维护
        }
    }
}


void init()
{
    memset(dfn, 0 , sizeof dfn ) ;
    memset(iscut , 0 , sizeof iscut ) ;
    memset(h,-1,sizeof h) ;
    child = idx = ts = ans  = 0; 
}

int main() 
{
    while(scanf("%d",&n) , n ) 
    {
        init() ;
        int a ;
        while(scanf("%d" ,&a),  a ) 
        {
            while(getchar() != '\n')
            {
                int b ;
                scanf("%d",&b) ;
                add(a,b) , add(b,a) ;
            }
        }


        int res = 0 ;
        // 如果整体不是连通图，那么有必要对每个root节点进行dfs
        // 但此题不用，因为题目给出的是连通图
        for( root = 1 ; root <=n ; root ++)  
        {
            if(!dfn[root]) 
            {
                tarjan(root) ;
                if(child > 1) res ++ ;  //如果当前root的child至少两个，那么root也是割点
            }
        }

        //等价于
        //root = 1 ;
        //tarjan(1) ;
        //if(child > 1) res ++ ;


        for(int i = 1 ; i <=n ; i ++ ) 
        {
            res += iscut[i] ;
        }
        printf("%d\n",res) ;
    }

    return 0 ;
}