uva315(求割点数目)

传送门:Network

题意:给出一张无向图,求割点的个数。

分析:模板裸题,直接上模板。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 110
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,next;
edge(){}
edge(int v,int next):v(v),next(next){}
}e[N*N];
int n,step,top,tot;
int head[N],dfn[N],low[N],Stack[N];
bool instack[N],cutpoint[N];
void init()
{
tot=;step=;top=;
FILL(head,-);FILL(dfn,);
FILL(low,);FILL(instack,false);
FILL(cutpoint,false);
}
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void tarjan(int u,int fa)
{
int son=;
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)continue;
if(!dfn[v])
{
son++;
tarjan(v,u);
if(low[u]>low[v])low[u]=low[v];
//割点: 一个顶点u是割点,当且仅当满足(1)或(2)
//(1) u为树根,且u有多于一个子树
//(2) u不为树根,且满足存在(u,v)为树枝边,使得DFS(u)<=Low(v)
if(u!=fa&&low[v]>=dfn[u])
{
cutpoint[u]=true;
}
}
else if(low[u]>dfn[v])
{
low[u]=dfn[v];
}
}
//树根,分支数大于1
if(u==fa&&son>)cutpoint[u]=true;
instack[u]=false;
top--;
}
void solve()
{
for(int i=;i<=n;i++)
if(!dfn[i])tarjan(i,i);
int ans=;
for(int i=;i<=n;i++)
if(cutpoint[i])ans++;
printf("%d\n",ans);
}
int main()
{
int u,v;
while(scanf("%d",&n),n)
{
init();
while(scanf("%d",&u),u)
{
while(getchar()!='\n')
{
scanf("%d",&v);
addedge(u,v);
addedge(v,u);
}
}
solve();
}
}
上一篇:js中三种全局变量声明方法


下一篇:《java入门第一季》之Arrays类前传(排序案例以二分查找注意的问题)