【求割点】Network

图论

传送门：POJ1144

题意：求一张无向图中割点的个数

思路：tarjan 对于点u：

  • 如果u为根，那么当且仅当u的子树（子连通分量？）的个数大于1时u为割点；
  • 如果u不为根，那么当且仅当存在u的子节点v满足low[v]>=dfn[u]时u为割点（u的子节点只能通过u来向上继续访问）

注意：读入和清空

代码大法好啊：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,ans,x,y,clock,rt,low[300],dfn[300];
bool G[300][300];
void init(){
	ans=clock=rt=0;
	memset(G,0,sizeof G);
	memset(dfn,0,sizeof dfn); memset(low,0,sizeof low);
}
void tarjan(int u){
	dfn[u]=low[u]=++clock; bool flag=0;
	for (int v=1;v<=n;v++)
		if (G[u][v]){
			if (!dfn[v]){
				if (u==1) rt++;
				tarjan(v);
				low[u]=min(low[u],low[v]);
				if (low[v]>=dfn[u]) flag=1;
			}
			else low[u]=min(low[u],dfn[v]);
		}
	if (flag) ans++;
}
int main(){
	while (scanf("%d",&n) && n){
		init();
		while (scanf("%d",&x) && x)
			while (getchar()!='\n'){
				scanf("%d",&y);
				G[x][y]=G[y][x]=1;
			}
			
		tarjan(1);
		if (rt<=1) ans--;
		printf("%d\n",ans);
	}
	
	return 0;
}