题意 ： 找出割点个数。
思路 ： Tarjan缩点，u是割点的充要条件是：u要么是具有两个以上子女的深度优先生成树的根，要么不是根，而有一个子女v满足low[v]>=dfn[u]。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 using namespace std ; 7 8 int head[1010],fb[1010],low[1010],dfn[1010]; 9 int cnt,timee ,ans,son ; 10 struct node 11 { 12 int u ; 13 int v ; 14 int next ; 15 }p[1010]; 16 17 void addedge(int u,int v) 18 { 19 p[cnt].u = u ; 20 p[cnt].v = v ; 21 p[cnt].next = head[u] ; 22 head[u] = cnt ++ ; 23 p[cnt].u = v ; 24 p[cnt].v = u ; 25 p[cnt].next = head[v] ; 26 head[v] = cnt ++ ; 27 } 28 void Init() 29 { 30 cnt = timee = ans = son = 0 ; 31 memset(head,-1,sizeof(head)) ; 32 memset(dfn,0,sizeof(dfn)) ; 33 memset(low,0,sizeof(low)) ; 34 memset(fb,0,sizeof(fb)) ; 35 } 36 37 void tarjan(int u) 38 { 39 dfn[u] = low[u] = ++timee ; 40 for(int i = head[u] ; i != -1 ; i = p[i].next) 41 { 42 int v = p[i].v ; 43 if(dfn[v]) low[u] = min(low[u],dfn[v]) ; 44 else 45 { 46 tarjan(v) ; 47 low[u] = min(low[v],low[u]) ; 48 if(low[v] >= dfn[u]) 49 { 50 if(u == 1) son ++ ; 51 else 52 fb[u] = 1 ; 53 } 54 } 55 } 56 } 57 int main() 58 { 59 int n,m,s ; 60 while(~scanf("%d",&n)) 61 { 62 if(n == 0 )break ; 63 Init() ; 64 while( ~scanf("%d",&m)) 65 { 66 if(m == 0) break ; 67 while(getchar() != ' ') 68 { 69 scanf("%d",&s) ; 70 addedge(s,m) ; 71 } 72 } 73 tarjan(1) ; 74 if(son > 1) ans ++ ; 75 for(int i = 1 ; i <= n ; i++) 76 if(fb[i]) ans ++ ; 77 printf("%d ",ans) ; 78 } 79 return 0 ; 80 }