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;
}