Cod sursa(job #1018649)

Utilizator Lucian-GeorgeFMI Popa Lucian George Lucian-George Data 29 octombrie 2013 20:55:23
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<iostream>
#include<fstream>
using namespace std;

int grad[50000],viz[50000],a[50000][5000],poz[50000],t=0,coada[50000],sf=0,nr=0,inc;

void push(int v[], int &sf, int x)
{
	sf++;
	v[sf]=x;
}
	
void dfs(int x)
{
	int i,j;
	for (i=1; i<=poz[x]; i++)
	{
		t++;
		if(viz[a[x][i]]==0) push(coada,sf,a[x][i]);
		viz[a[x][i]]+=t;
		grad[a[x][i]]=viz[a[x][i]];
		dfs(a[x][i]);
		//t--;
	}
}
	     
int main()
{
	int n,m,i,j,x,y;
	
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	
	f>>n>>m;
	for (i=1; i<=m; i++)
	{
		f>>x>>y;
		poz[x]++;
		grad[y]++;
		a[x][poz[x]]=y;
	}
	for (i=1; i<=n; i++)
		if (grad[i]==0) {
			push(coada,sf,i);
			g<<i<<" ";
			dfs(i);
		}

	for (i=1; i<=sf; i++) if (grad[coada[i]]==0) inc=i+1; 
	
	//while (nr<n)
	{
		while (inc<=sf)
			{
				grad[coada[inc]]--;
				if (grad[coada[inc]]==0)
				{
					g<<coada[inc]<<" ";
					nr++;
					t=0;
					dfs(coada[inc]);
					inc++;
				}
			}
	}
				
	//for (i=1; i<=n; i++) cout<<viz[i]<<"\n";
	//for (i=1; i<=sf; i++) cout<<coada[i]<<" ";
	return 0;
}