Cod sursa(job #1019286)

Utilizator Lucian-GeorgeFMI Popa Lucian George Lucian-George Data 30 octombrie 2013 21:28:41
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 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,n;

void push(int v[], int &sf, int x)
{
	sf++;
	v[sf]=x;
}
	
void dfs(int x)
{
	int i,j;
	t++;
	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]]=t;}
		else
		if (t<grad[a[x][i]]) grad[a[x][i]]=t;
		dfs(a[x][i]);
	}
	t--;
}
	     
int main()
{
	int 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<<" ";
			nr++;
			dfs(i);
		}

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