Cod sursa(job #669796)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 27 ianuarie 2012 19:40:02
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;

bool a[20005][20005];
int k,D[100],m;
set<int> S;
vector<int> L;

int main()
{
	int n;
	/* Kahn */
	freopen("sortaret.in","r", stdin);
	freopen("sortaret.out","w", stdout);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		a[x][y]=true;
		D[y]=D[y]+a[x][y];

	}
	fclose(stdin);	
	
	k=0;
	for(int i=1;i<=n;i++) if(D[i]==0) S.insert(i);
	
	int v;
	while(!S.empty())
	{
		v=*S.begin();
		L.push_back(v);
		S.erase(v);
		for(int i=1;i<=n;i++)
			if(a[v][i]==1)
			{
				a[v][i]=0;
				D[i]--;
				if(D[i]==0) 
				{
					S.insert(i);
				}
			}
	}
	//if(L.size()<n) cout<<" exista circuite";
	for(unsigned int i=0;i<L.size();i++)
	{
		printf("%d ",L[i]);
		
	}
	return 0;
}