poj 1144(割点）

题意：给出一个无向图，求关键节点的个数。
分析：双连通分量Tarjan算法直接求割点就行了，裸的模板题。
AC代码：
 1 #include<cstdio>
 2 #include<cstring>
 3 const int N=105;
 4 struct EDGE{
 5     int v,next;
 6 }edge[N*N];
 7 int first[N],low[N],dfn[N];
 8 bool cut[N];
 9 int rt,son,g,cnt;
10 int min(int a,int b)
11 {
12     return a<b?a:b;
13 }
14 void AddEdge(int u,int v)
15 {
16     edge[g].v=v;
17     edge[g].next=first[u];
18     first[u]=g++;
19 }
20 void Tarjan(int u)
21 {
22     int i,v;
23     dfn[u]=low[u]=++cnt;
24     for(i=first[u];i!=-1;i=edge[i].next)
25     {
26         v=edge[i].v;
27         if(!dfn[v])
28         {
29             Tarjan(v);
30             if(u==rt)
31                 son++;
32             else
33             {
34                 low[u]=min(low[u],low[v]);
35                 if(low[v]>=dfn[u])
36                     cut[u]=true;
37             }
38         }
39         else
40             low[u]=min(low[u],dfn[v]);
41     }
42 }
43 int main()
44 {
45     int n,i,u,v;
46     char c;
47     while(scanf("%d",&n)&&n)
48     {
49         g=cnt=0;
50         memset(first,-1,sizeof(first));
51         memset(low,0,sizeof(low));
52         memset(dfn,0,sizeof(dfn));
53         memset(cut,false,sizeof(cut));
54         while(scanf("%d",&u)&&u)
55         {
56             while(1)
57             {
58                 scanf("%d%c",&v,&c);
59                 AddEdge(u,v);
60                 AddEdge(v,u);
61                 if(c!=' ')
62                     break;
63             }
64         }
65         rt=1;
66         son=0;
67         Tarjan(1);
68         if(son>1)
69             cut[1]=true;
70         int ans=0;
71         for(i=1;i<=n;i++)
72             if(cut[i])
73                 ans++;
74         printf("%d
",ans);
75     }
76     return 0;
77 }
View Code