POJ 1144 Network(双连通+割点)
割点
将这个点去掉,图就会被分成两个部分(或者以上),那么这个点就是一个割点
判断割点
- 对根节点u,若其有两棵或两棵以上的子树,则该根结点u为割点;
- 对非叶子节点u(非根节点),若其子树的节点均没有指向u的祖先节点的回边,说明删除u之后,根结点与u的子树的节点不再连通;则节点u为割点。
POJ 1144 Network(求割点个数)
#include <stack>
#include <vector>
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
bool flag[105];
int ans, cnt, low[105], time[105];
vector<int> v[105];
void init()
{
ans = cnt = 0;
memset(flag, 0, sizeof(flag));
memset(low, 0, sizeof(low));
memset(time, 0, sizeof(time));
for(int i = 0; i <= 104; ++i)
v[i].clear();
}
void Trajan(int x, int pre)
{
int tem, sum = 0;
low[x] = time[x] = ++cnt;
for(int i = 0; i < v[x].size(); ++i)
{
tem = v[x][i];
if(!time[tem])
{
Trajan(tem, x);
low[x] = min(low[x], low[tem]);
sum++;
if(x != pre && low[tem] >= time[x])
flag[x] = 1;
if(x == pre && sum > 1)
flag[x] = 1;
}
else
low[x] = min(low[x], time[tem]);
}
}
int main()
{
int n;
while(~scanf("%d", &n) && n)
{
init();
int u, to;
while(~scanf("%d", &u) && u)
{
getchar();
char ch;
while(1)
{
scanf("%d%c", &to, &ch);
v[u].push_back(to);
v[to].push_back(u);
if(ch == '\n')
break;
}
}
Trajan(1, 1);
// for(int i = 1; i <= n; ++i)
// if(!time[i])
// Trajan(i, i);
for(int i = 1; i <= n; ++i)
if(flag[i])
ans++;
cout << ans << '\n';
}
return 0;
}
割点可能被重复标记,所以不能在找到割点时计数
而必须找出所有割点再数出个数