[ Bridge & Bridge-connected Component ] 橋和橋連通分量(BCC)

只要從一張無向圖上移除了橋，就會讓這張圖分離成更多部分，呈現不連通的狀態。
注意！必須要考慮重邊的問題:

1. 對於有向圖的強連通分量，重邊是沒有影響的，因為強連通只要求任意兩點可以互相連通
2. 對於無向圖的點雙連通分量，重邊也是沒有影響的，因為點雙連通要求是任意兩點之間至少存在兩條點不重複的路徑，對邊的重複並沒有要求
3. 對於無向圖的邊雙連通分量，重邊就有影響了，因為邊雙連通要求任意兩點之間至少存在兩條邊不重複的路徑

這裡提供模板:

	#include<vector>
	#include<algorithm>
	#define N 1005
	struct edge{
	int u,v;
	bool is_bridge;
	edge(int u=0,int v=0):u(u),v(v),is_bridge(0){}
	};
	std::vector<edge> E;
	std::vector<int> G[N];// 1-base
	int low[N],vis[N],Time,bridge_cnt;
	inline void add_edge(int u,int v){
	G[u].push_back(E.size());
	E.push_back(edge(u,v));
	G[v].push_back(E.size());
	E.push_back(edge(v,u));
	}
	void dfs(int u,int re=-1){//u當前點，re為u連接前一個點的邊
	int v;
	low[u]=vis[u]=++Time;
	st[top++]=u;
	for(size_t i=0;i<G[u].size();++i){
	int e=G[u][i];v=E[e].v;
	if(!vis[v]){
	dfs(v,e^1);//e^1反向邊
	low[u]=std::min(low[u],low[v]);
	if(vis[u]<low[v]){
	E[e].is_bridge=E[e^1].is_bridge=1;
	++bridge_cnt;
	}
	}else if(vis[v]<vis[u]&&e!=re)
	low[u]=std::min(low[u],vis[v]);
	}
	}

view raw bridge.cpp hosted with ❤ by GitHub

一張無向圖上，不會產生橋的連通分量，稱作橋連通分量，或是橋雙連通分量
這裡提供模板，code跟橋差不多，只是需要用堆疊去記錄當前節點而已:

	#include<vector>
	#include<algorithm>
	#define N 1005
	struct edge{
	int u,v;
	bool is_bridge;
	edge(int u=0,int v=0):u(u),v(v),is_bridge(0){}
	};
	std::vector<edge> E;
	std::vector<int> G[N];// 1-base
	int low[N],vis[N],Time;
	int bcc_id[N],bridge_cnt,bcc_cnt;// 1-base
	int st[N],top;//BCC用
	inline void add_edge(int u,int v){
	G[u].push_back(E.size());
	E.push_back(edge(u,v));
	G[v].push_back(E.size());
	E.push_back(edge(v,u));
	}
	void dfs(int u,int re=-1){//u當前點，re為u連接前一個點的邊
	int v;
	low[u]=vis[u]=++Time;
	st[top++]=u;
	for(size_t i=0;i<G[u].size();++i){
	int e=G[u][i];v=E[e].v;
	if(!vis[v]){
	dfs(v,e^1);//e^1反向邊
	low[u]=std::min(low[u],low[v]);
	if(vis[u]<low[v]){
	E[e].is_bridge=E[e^1].is_bridge=1;
	++bridge_cnt;
	}
	}else if(vis[v]<vis[u]&&e!=re)
	low[u]=std::min(low[u],vis[v]);
	}
	if(vis[u]==low[u]){//處理BCC
	++bcc_cnt;// 1-base
	do bcc_id[v=st[--top]]=bcc_cnt;//每個點所在的BCC
	while(v!=u);
	}
	}
	inline void bcc_init(int n){
	Time=bcc_cnt=bridge_cnt=top=0;
	E.clear();
	for(int i=1;i<=n;++i){
	G[i].clear();
	vis[i]=0;
	bcc_id[i]=0;
	}
	}

view raw BCC.cpp hosted with ❤ by GitHub