المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر
دنبال کنندگان ۳ نفر
این وبلاگ را دنبال کنید

Topological Sorting - مرتب سازی توپولوژیکی

چهارشنبه, ۱۸ بهمن ۱۳۹۱، ۰۵:۲۹ ب.ظ

شرح مساله(ویکی پدیا) :

« در نظریه گرافها، یک مرتب سازی موضعی یا ترتیب موضعی یک گراف بدون دور جهت دار، یک ترتیب خطی از همه رئوس آن است به طوری که هر گره قبل از همه گره‌هایی می‌آید که از آن به آنها یال خارج شده است. »

 

شرح الگوریتم : 

در هر مرحله می توانیم راس هایی را که هیچ یال ورودی ایی ندارند را در لیست قرار بدهیم

پس در هر مرحله همه راس هایی که هیچ یال ورودی ندارند (درجه ورودی آنها صفر است) را در لیست قرار می دهیم و لیست جدیدی از راس هایی که با حذف راس های قبلی درجه ورودی آنها صفر شده است درست می کنیم . حالا الگوریتم رو روی گراف جدید و با لیست جدید دوباره تکرار می کنیم .

اینکار را تا زمانی انجام می دهیم که دیگر راسی با درجه ورودی صفر وجود نداشته باشد ، به عبارتی دیگر یا همه راس های گراف را در لیست وارد کرده باشیم یا اینکه در گراف به یک دور رسیده باشیم (این یعنی یک مرتب سازی توپولوژیکی در گراف وجود ندارد )(چرا ؟)

در نهایت اگر اندازه لیست برابر با تعداد راس های گراف اولیه بود ، ما یک مرتب سازی توپولوژیکی برای گراف پیدا کرده ایم و در غیر این صورت ، گراف دارای دور است و فاقد یک مرتب سازی توپولوژیکی .

واضح است که الگوریتم ارایه شده از است .

کد ++C :

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 1e5;
vector<int> outro[MAX];
int intro[MAX];
bool vis[MAX];
int main(){
    int v,e;
	cin>>v>>e;
	for(int i=0;i<e;i++){
		int a,b;
		cin>>a>>b;
		outro[a].push_back(b);
		intro[b]++;
	}
	vector<int> can;
	vector<int> ans;
	for(int i=1;i<=v;i++){
		if(intro[i]==0)
			can.push_back(i);	
	}
	while(can.size()){
		vector<int> ncan;
		for(int i=0;i<can.size();i++){
			ans.push_back(can[i]);
			for(int j=outro[can[i]].size()-1;j>=0;j--){
				intro[outro[can[i]][j]]--;
				outro[can[i]].pop_back();
				if(!intro[outro[can[i]][j]])
					ncan.push_back(outro[can[i]][j]);
			}
		}
		can=ncan;
	}
	if(ans.size()==v){
		for(int i=0;i<ans.size();i++)
			cout<<ans[i]<<" ";
		cout<<endl;
	}
	else{
		cout<<"Impossible"<<endl;
	}
	return 0;
}

 بر گرفته از challenger.blog.ir(محمد مهدی جهان آرا)

نظرات (۰)

هیچ نظری هنوز ثبت نشده است
ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی