割点模板

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=1e3+10;
 6 
 7 int dfn[maxn],low[maxn],head[maxn],vis[maxn];
 8 bool judge[maxn];
 9 int k,n,num,root;
10 
11 struct Edge{
12     int to,next;
13 }G[maxn<<1];
14 
15 void build(int u,int v){
16     G[num].to=v;G[num].next=head[u];head[u]=num++;
17 }
18 
19 void Tarjan(int u,int fa){
20     int son=0;
21     vis[u]=1;    //判断是否访问过，当访问完后定为2，不再访问；
22     k++;
23     dfn[u]=k;    //当前顶点的时间戳
24     low[u]=k;    //当前顶点能够访问到的最小时间戳 一开始是自己
25     for(int i=head[u];i!=-1;i=G[i].next){
26         int v=G[i].to;
27         //如果定点i曾经被访问过，并且这个定点不是当前u的父亲，就说明
28         //此时的i为U的祖先,所以更新u的权值
29         if(vis[v]==1&&v!=fa)
30             low[u]=min(low[u],dfn[v]);
31         if(vis[v]==0){
32             Tarjan(v,u);
33             son++;
34             //更新当前顶点u能访问到的最早顶点的时间戳；
35             low[u]=min(low[u],low[v]);
36             //如果是根节点，就必须要有两个儿子才会使割点；
37             //不是根节点，就要满足dfn[u]<=low[v]
38             if((u==root&&son>1)||(u!=root&&dfn[u]<=low[v]))
39                 judge[u]=1;
40         }
41     }
42     vis[u]=2;
43 }
44 
45 int main(){
46     while(~scanf("%d",&n) && n){
47         memset(head,-1,sizeof(head));
48         memset(dfn,0,sizeof(dfn));
49         memset(low,0,sizeof(low));
50         memset(vis,0,sizeof(vis));
51         memset(judge,0,sizeof(judge));
52         num=0;
53         int u,v;
54         while(scanf("%d",&u)&&u){
55             while(getchar()!=‘\n‘){
56                 scanf("%d",&v);
57                 build(u,v);
58                 build(v,u);
59             }
60         }
61         root=1;
62         Tarjan(root,-1);
63         int ans=0;
64         for(int i=1;i<=n;i++)
65             if(judge[i]){
66              //   printf("%d\n",i);
67                 ans++;
68             }
69         printf("%d\n",ans);
70     }
71     return 0;
72 }