Cod sursa(job #631698)

Utilizator stephy_yoyoIonescu Stefania stephy_yoyo Data 9 noiembrie 2011 16:57:31
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
# include <cstdio>
# include <vector>
using namespace std;

vector<int> v[50001],c;
int nrintrare[50001];
char fr[50001];

int main ()
{
	freopen ("sortaret.in","r",stdin);
	freopen ("sortaret.out","w",stdout);
	int n,m,nod,x,y,in;
	scanf ("%d%d",&n,&m);
	for (int i=1; i<=m;i++)
	{
		scanf ("%d%d",&x,&y);
		v[x].push_back(y);
		nrintrare[y]++;
		//vi[y].push_back(x);
	}
	for (int i=1;i<=n;i++)
		if (!nrintrare[i])
		{
			printf ("%d ",i);
			c.push_back(i);
			fr[i]=1;
		}
	for (in=0;in<c.size();in++)
	{
		nod=c[in];
		for (int i=0;i<v[nod].size();i++)
			if (!fr[v[nod][i]])
				nrintrare[v[nod][i]]--;
		for (int i=1;i<=n;i++)
			if (!nrintrare[i] && !fr[i])
			{
				printf ("%d ",i);
				c.push_back(i);
				fr[i]=1;
			}
	}
	return 0;
}