UVA315 (无向图求割点)

题目大意:给定一个无向图,问共存在多少个割点。(割点:去掉此点后此图会断开连接)割点有两种存在:一种是第一次搜索的根节点,若其子节点数超过两个,则此点去掉后图会

断开连接,因此此点为割点;或者此点为搜索树的子节点,若其子节点的最早达到时间状态比其自身要晚,则说明此点不得不经过,并以此来更新其子节点,故其也是割点。

详见代码。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
#define N 10100
vector<vector<int> >G;
int n, dfn[N], low[N], Time, father[N], vis[N];
void Init()
{
G.clear();
G.resize(n+);
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
memset(father, , sizeof(father));
memset(vis, , sizeof(vis));
Time = ;
}
void Trajin(int u, int fa)
{
father[u] = fa;
dfn[u] = low[u] = ++Time;
int i, len = G[u].size(), v;
for(i=; i<len; i++)
{
v = G[u][i];
if(!dfn[v])
{
Trajin(v, u);
low[u] = min(low[u], low[v]);
}
else if(fa!=v)
low[u] = min(low[u], dfn[v]);
}
}
int main()
{
while(scanf("%d", &n), n)
{
Init();
int a, b;
char x;
while(scanf("%d", &a), a)
{
while(scanf("%d%c", &b, &x))
{
G[a].push_back(b);
G[b].push_back(a);
if(x=='\n')break;
}
}
Trajin(, );
int ans = , RootSon = ;
for(int i=; i<=n; i++)
{
if(father[i]==)RootSon++;
else if(dfn[father[i]]<=low[i])
vis[father[i]] = ;
}
if(RootSon>)ans++;
for(int i=; i<=n; i++)
if(vis[i])ans++;
printf("%d\n", ans);
}
return ;
}
上一篇:迷你MVVM框架 avalonjs 0.95发布


下一篇:UVA315 Network —— 割点