Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم های تکمیلی:پیدا کردن یال برشی

پیدا کردن یال برشی

برای پیدا کردن یال برشی، ابتدا بر روی گراف الگوریتم DFS را اجرا می کنیم. در هنگام اجرا شدن الگوریتم DFS به ازای هر راس i یک مقدار dp[i] نگه می داریم که نشان دهنده ی این است که در زیر درخت راس i، بالا ترین backedge به چه ارتفاعی وصل می شود. مقدار dp[i] برای هر راس این گونه حساب می شود که مقدار یک راس برابر خواهد شد با ماکسیمم مقداری که فرزندان آن راس دارند و یال هایی که از خود آن راس به پدرانش وصل است. حال یک یال که بین راس v و parent[v] برشی است اگر و فقط اگر dp[v] مقدارش بالا تر از ارتفاع v نباشد. یعنی یالی در زیر درخت v وجود نداشته باشد که به راسی بالا تر از v وصل باشد.

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

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

#include<iostream>
#include<vector>
 
using namespace std;
 
const int maxn=1000000+10;
 
bool mark[maxn],is[maxn];
int dp[maxn],h[maxn];
pair<int,int> edge[maxn];
vector<pair<int,int> > adj[maxn];
 
void dfs(int v,int parent,int index){
	dp[v]=h[v];
	mark[v]=true;
	for(int i=0;i<adj[v].size();i++){
		int u=adj[v][i].first;
		int ind=adj[v][i].second;
		if(!mark[u]){
			h[u]=h[v]+1;
			dfs(u,v,ind);
			dp[v]=min(dp[v],dp[u]);
		}
		else{
			if(u!=parent){
				dp[v]=min(dp[v],h[u]);
			}
		}
	}
	if(v!=1){
		if(dp[v]==h[v]){
			is[index]=true;
		}
	}
	return;
}
 
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		edge[i]=make_pair(u,v);
		adj[u].push_back(make_pair(v,i));
		adj[v].push_back(make_pair(u,i));
	}
	dfs(1,0,0);
	for(int i=0;i<m;i++){
		if(is[i]){
			cout<<edge[i].first<<" "<<edge[i].second<<endl;
		}
	}
	return 0;
}

ابزار صفحه