Cod sursa(job #690955)

Utilizator i.anna_mIlusca Ana-Maria i.anna_m Data 26 februarie 2012 08:20:05
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
FILE *f,*g;
vector<int> viz(50001);
vector <int> grad(50001);
vector <vector<int> > q(50001,vector<int> (1,0));
vector <int> gradint(50001);
vector <int> arr;
int n,m;
int main()
{
	int k=0;
	f=fopen("sortaret.in","r");
	g=fopen("sortaret.out","w");
	fscanf(f,"%d%d",&n,&m);
	int i,a,b;
	for(i=0;i<m;i++)
	{
		fscanf(f,"%d%d",&a,&b);
		q[a].push_back(b);
		grad[b]++;
		gradint[a]++;
	}
	for(i=1;i<=n;i++)
		if(grad[i]==0)
		{
			arr.push_back(i);
			k++;
			viz[i]=1;
		}
		int u,x;
	for(x=0;x<k;x++)
	{
		i=arr[x];
		for(u=1;u<=gradint[i];u++)
		{
			--grad[q[i][u]];
			if(grad[q[i][u]]==0 && viz[q[i][u]]==0)
			{
				arr.push_back(q[i][u]);
				++k;
				viz[q[i][u]]=1;
			}
		}
	}
	for(i=0;i<k;i++)
		fprintf(g,"%d ",arr[i]);
	fclose(f);
	fclose(g);
	return 0;	
}