POJ 1144

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

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

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

Tarjan算法求割点的办法

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

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

 #include <stdio.h>
#include <stack>
#include <string.h>
#define maxn 505 using namespace std; stack <int >s; int head[maxn],n,pos,dfn[maxn],low[maxn],bcnt,dindex,num[maxn],root; bool vis[maxn]; struct node{
int next,to;
}edge[maxn]; void add(int u,int v)
{
edge[pos].to = v;
edge[pos].next = head[u];
head[u] = pos++;
} void Tarjan(int u)
{
dfn[u] = low[u] = ++dindex;
vis[u] = true;
s.push(u);
for(int i = head[u]; i != - ; i = edge[i].next)
{
int v = edge[i].to;
if(!vis[v])
{
Tarjan(v);
if(low[v]<low[u]) low[u] = low[v];
if(low[v]>=dfn[u]&&u!=)
{
num[u]++;
}else if(u==)
root++;
}else if(dfn[v]<low[u])
low[u] = dfn[v];
}
} int main()
{
int u,v,ans;
// freopen("in.txt","r",stdin);
while(scanf("%d",&n),n)
{ memset(head,-,sizeof(head));
memset(vis,false,sizeof(vis));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(num,,sizeof(num));
pos = ;
ans = ;
while(scanf("%d",&u)&&u)
{
while(getchar()!='\n')
{
scanf("%d",&v);
add(u,v);
add(v,u);
}
}
bcnt = dindex = root=;
for(int i = ;i<=n;i++)
if(!dfn[i]) Tarjan(i);
for(int i = ; i<=n;i++)
if(num[i]) ans++;
if(root>) ans++;
printf("%d\n",ans);
}
return ;
}

https://www.byvoid.com/blog/scc-tarjan/一个很好的学习Tarjan的博客

上一篇:使用Java程序片段动态生成表格


下一篇:poj 1144 Network 图的割顶判断模板