kuangbin专题 专题九 连通图 Network UVA - 315

题目链接：https://vjudge.net/problem/UVA-315

题目：求割点。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int N = ;

 int n,tim,tot,root = ;

 int head[N],dfn[N],low[N],poi[N];

 struct node{

     int to;

     int nxt;

 }e[N*N];

 void init(){

     for(int i = ; i <= n; ++i){

         head[i] = -;

         dfn[i] = poi[i] = ;

     }

     tim = tot = ;

 }

 inline void add(int u,int v){

     e[tot].to = v;

     e[tot].nxt = head[u];

     head[u] = tot++;

 }

 void tarjan(int now,int pre){

     dfn[now] = low[now] = ++tim;

     int to,son = ;

     for(int o = head[now]; ~o; o = e[o].nxt){

         to = e[o].to;

         if(to == pre) continue; //处理无向图的双向边问题

         if(!dfn[to]){

             ++son;

             tarjan(to,now);

             low[now] = min(low[now],low[to]);

             //割点条件1

             if(now != root && dfn[now] <= low[to]) poi[now] = ;

         }

         else if(low[now] > dfn[to]) low[now] = dfn[to];

     }

     //割点条件2

     if(now == root && son >= ) poi[now] = ;

 }

 int main(){

     int u,v;

     char ch;

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

         init();

         while(~scanf("%d",&u) && u){

             while(~scanf("%d%c",&v,&ch)){

                 add(u,v); add(v,u);

                 if(ch == '\n') break;

             }

         }

         tarjan(,);

         int ans = ;

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

             if(poi[i]) ++ans;

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

     }

     return ;

 }