[kuangbin帶你飛]專題九 連通圖 B - Network 割點

無向圖的割點（橋），具體的要用到tarjan三大算法之一。

下面貼出模闆：

#include<bits/stdc++.h>
using namespace std;

#define pb(a) push_back(a)
const int maxn = 105;
int n,low[maxn],dfn[maxn],f[maxn],cut[maxn],times;  
vector<vector<int> > g;

void init() {
	g.clear();
	g.resize(n+1);
	memset(low,0,sizeof(low));  //該點能到達之前點的最早時間
	memset(dfn,0,sizeof(dfn)); //最先到達該點的時間
	memset(f,0,sizeof(f)); //儲存一個點的父節點
	memset(cut,0,sizeof(cut)); //該點是否為割點。
	times = 0;
}

void tarjan(int u,int fa) {
	int len,v;
	low[u] = dfn[u] = ++times;
	f[u] = fa;
	len = g[u].size();
	for(int i = 0;i < len;i++) {
		v = g[u][i];
		if(!dfn[v]) {
			tarjan(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) != EOF && n) {
		int a,b; char c;
		init();
		while(scanf("%d",&a) != EOF && a) {
			while(scanf("%d%c",&b,&c)) {
				g[a].pb(b);
				g[b].pb(a);	
				if(c == '\n') break;
			}
		}
		int rootson = 0,v,ans = 0;
		tarjan(1,0);
		for(int i = 2;i <= n;i++) {
			v = f[i];
			if(v == 1) rootson++;
			else if(dfn[v] <= low[i]) cut[v] = 1;
		}
		for(int i = 2;i <= n;i++) 
			if(cut[i]) ans++;
		if(rootson > 1) ans++;
		printf("%d\n",ans);
	}
}