博客

POJ 1144

  • Post author:
  • Post category:其他



http://poj.org/problem?id=1144

题意：给你一些点，某些点直接有边，并且是无向边，求有多少个点是割点

割点：就是在图中，去掉一个点，无向图会构成多个子图，这就是割点

Tarjan算法求割点的办法

  1. 如果该点为根，那么它的子树必须要大于1
  2. 如果该点不为根，那么当low[v]>=dnf[u]时，为割点

Low[v]>=dnf[u]也就是说明U的子孙点只能通过U点访问U的祖先点 

 1 #include <stdio.h>
 2 #include <stack>
 3 #include <string.h>
 4 #define maxn 505
 5 
 6 using namespace std;
 7 
 8 stack <int >s;
 9 
10 int head[maxn],n,pos,dfn[maxn],low[maxn],bcnt,dindex,num[maxn],root;
11 
12 bool vis[maxn];
13 
14 struct node{
15     int next,to;
16 }edge[maxn];
17 
18 void add(int u,int v)
19 {
20     edge[pos].to = v;
21     edge[pos].next = head[u];
22     head[u] = pos++;
23 }
24 
25 void Tarjan(int u)
26 {
27     dfn[u] = low[u] = ++dindex;
28     vis[u] = true;
29     s.push(u);
30     for(int i = head[u]; i != -1 ; i = edge[i].next)
31     {
32         int v = edge[i].to;
33         if(!vis[v])
34         {
35             Tarjan(v);
36             if(low[v]<low[u]) low[u] = low[v];
37             if(low[v]>=dfn[u]&&u!=1)
38             {
39                 num[u]++;
40             }else if(u==1)
41                 root++;
42         }else if(dfn[v]<low[u])
43             low[u] = dfn[v];
44     }
45 }
46 
47 int main()
48 {
49     int u,v,ans;
50   //  freopen("in.txt","r",stdin);
51     while(scanf("%d",&n),n)
52     {
53 
54         memset(head,-1,sizeof(head));
55         memset(vis,false,sizeof(vis));
56         memset(dfn,0,sizeof(dfn));
57         memset(low,0,sizeof(low));
58         memset(num,0,sizeof(num));
59         pos = 1;
60         ans = 0;
61         while(scanf("%d",&u)&&u)
62         {
63             while(getchar()!='\n')
64             {
65                 scanf("%d",&v);
66                 add(u,v);
67                 add(v,u);
68             }
69         }
70         bcnt = dindex = root=0;
71         for(int i = 1;i<=n;i++)
72             if(!dfn[i]) Tarjan(i);
73         for(int i = 1 ; i<=n;i++)
74             if(num[i]) ans++;
75         if(root>1) ans++;
76         printf("%d\n",ans);
77     }
78     return 0;
79 }


https://www.byvoid.com/blog/scc-tarjan/

一个很好的学习Tarjan的博客

转载于:https://www.cnblogs.com/Tree-dream/p/6051765.html