Cod sursa(job #917585)

Utilizator nutipasa16Macovei Claudiu nutipasa16 Data 18 martie 2013 09:38:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n,m,x,y,viz[50002],grad[50002];
vector<int> v[50002],sol;
queue <int> Q;
void dfs()
{
	int x;
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		if(!viz[x])
		{
			g<<x<<" ";
			viz[x]=1;
			for(unsigned int j=0;j<v[x].size();j++)
			{
				grad[v[x][j]]--;
				if(grad[v[x][j]]==0)
					Q.push(v[x][j]);
			}
		}
	}
}
int main()
{
	f>>n>>m;
	for(int i=1;i<=m;i++)
	{
		f>>x>>y;
		v[x].push_back(y);
		grad[y]++;
	}
	for(int i=1;i<=n;i++)
		if(grad[i]==0)
			Q.push(i);
	dfs();
}