اُپدیا

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

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

زمان اجرای این الگوریتم مانند زمان اجرای الگوریتم پیدا کردن راس برشی است یعنی $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;
}