[POJ 1144] Network【Tarjan割点】

• 2018-01-09
• 0
• 0

Problem:

Description

Input

Output

Sample Input

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0

Sample Output

1
2

Hint

Source

Solution:

Tarjan 求割点的模板题。

割点 (Cut vertices / Articulation points) 是指在一个连通的无向图 G 的顶点集 V 中的部分顶点，其中任意一个去除后能导致 G 不再连通。

利用 Tarjan 算法时间戳 dfn[] 的特性，我们可以构建出一棵解答树（可以理解成 dfs 树，在原图的基础上去掉了没有走过的边）。

这样的话，考虑到回边（即返祖边）的存在，一个节点的任意两棵子树都只能通过该节点或该节点的祖先相连通。

在这棵解答树上，割点的存在分两种情况：

1. 根节点是割点，当且仅当它至少有 2 棵子树。此时若删去该节点，它的任意两棵子树不再连通。
2. 非根节点是割点，当且仅当它的某一棵子树没有指向它的祖先的边。此时若删去该节点，该子树与其他部分不再连通。

第 1 种情况很好实现。而第 2 种情况正好可以利用 Tarjan 算法的 dfn[] 和 low[]，当节点 u 到它的子节点 v 的递归返回后若

• low[v] ≥ dfn[u]

则从 v 出发不能到达 u 的祖先，因为 u 的祖先的时间戳一定比 u 的时间戳更小。

至此，Tarjan 算法求割点的任务圆满完成。

伪代码参见 https://en.wikipedia.org/wiki/Biconnected_component

Code: O(T(N+M)), M为总边数 [144K, 16MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N;

struct Edge{
	int np;
	Edge *nxt;
};

struct Graph{
	Edge *V[102], E[10002];
	int tope;
	
	inline void clear() {tope = 0, memset(V, 0, sizeof(V));}
	
	inline void addedge(int u, int v) {E[++tope].np = v, E[tope].nxt = V[u], V[u] = &E[tope];}
} G;

int dfn[102], dfstime;
int low[102];
int vis[102], rootchild;
bool Artic[102];

inline void Tarjan(int u){
	dfn[u] = low[u] = ++dfstime, vis[u] = 1;
	for(register Edge *ne = G.V[u]; ne; ne = ne->nxt){
		if(!vis[ne->np]){
			Tarjan(ne->np);
			if(u == 1) {if(++rootchild > 1) Artic[1] = 1;}
			else{
				if(low[ne->np] >= dfn[u]) Artic[u] = 1;
				low[u] = min(low[u], low[ne->np]);
			}
		}
		else low[u] = min(low[u], dfn[ne->np]);
	}
}

int main(){
	while(scanf("%d", &N) != EOF && N){
		{
			int u, v;
			G.clear();
			while(scanf("%d", &u) != EOF && u){
				while(getchar() != '\n'){
					scanf("%d", &v);
					G.addedge(u, v), G.addedge(v, u);
				}
			}
		}  // Limit the action scope of the variables u and v
		dfstime = 0, rootchild = 0;
		memset(vis, 0, sizeof(vis));
		memset(Artic, 0, sizeof(Artic));
		for(register int i = 1; i <= N; i++)
			if(!vis[i]) Tarjan(i);
		int ans = 0;
		for(register int i = 1; i <= N; i++)
			if(Artic[i]) ans++;
		printf("%d\n", ans);
	}
	return 0;
}