المپدیا

مولفه های دو همبند

به یک گراف دوهمبند می گویند اگر هیچ راس برشی در آن وجود نداشته باشد. برای پیدا کردن مولفه های دو همبند کافی است که راس های برشی گراف را پیدا کنیم وسعی کنیم گراف را به مجموعه ای از یال ها افزاز کنیم که هر دو یالی که در یک مجموعه قرار می گیرند در یک دور باهم آمده باشند. برای به دست آوردن راس های برشی نیز به مانند همان الگوریتم پیدا کردن راس برشی عمل می کنیم.

زمان اجرای این الگوریتم مانند زمان اجرای الگوریتم پیدا کردن راس برشی است یعنی $O(n+m)$ است. ( $n$ نشان دهنده تعداد راس ها و $m$ نشان دهنده تعداد یال ها است.)

پیاده سازی الگوریتم در کد زیر آمده است.

#include<iostream>
#include<vector>
#include<stack>
 
using namespace std;
 
const int maxn=1000000+10;
 
vector<int> adj[maxn];
bool vis[maxn];
int n, e, dep[maxn], par[maxn], lowlink[maxn];
vector<vector <int> > comp;
stack<int> st;
void dfs (int u, int depth = 0, int parent = -1) {
	vis[u] = true; dep[u] = depth; par[u] = parent;
	lowlink[u] = depth; st.push (u);
	for (int i = 0; i < (int)adj[u].size(); i++) {
		int v = adj[u][i];
		if (!vis[v]) {
			dfs (v, depth + 1, u);
			lowlink[u] = min (lowlink[u], lowlink[v]);
		}
		else lowlink[u] = min (lowlink[u], dep[v]);
	}
	if (lowlink[u] == dep[u] - 1) { // comp
		comp.push_back (vector <int> ());
		while (st.top() != u) {
			comp.back().push_back (st.top());
			st.pop();
		}
		comp.back().push_back (u);
		st.pop();
		comp.back().push_back (par[u]);
	}
}
void bicon () {
	for (int i = 1; i <= n; i++)
		if (vis[i] == false) dfs (i);
}
int main(){
	cin>>n>>e;
	for(int i=0;i<e;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	bicon();
	for(int i=0;i<comp.size();i++){
		for(int j=0;j<comp[i].size();j++){
			cout<<comp[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}