Cod sursa(job #676238)

Utilizator costyv87Vlad Costin costyv87 Data 8 februarie 2012 21:14:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#include <list>
#define nmax 50010
using namespace std;
list  <int> a[nmax];
list <int> sol;
int gr[nmax];
FILE *f,*g;
int n,m;

void read() {
int i,x,y;
f=fopen("sortaret.in","r");
g=fopen("sortaret.out","w");

fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;i++) {
	fscanf(f,"%d%d",&x,&y);
	gr[y]++;
	a[x].push_back(y);
	}
}

void solve() {
int i;
	
for (i=1;i<=n;i++) 
	if (!gr[i]) 
		sol.push_back(i);

for (list <int>::iterator p=sol.begin();p!=sol.end();p++) 
	for (list <int>::iterator q=a[*p].begin();q!=a[*p].end();q++) {
		gr[*q]--;
		if (gr[*q]==0) {
			sol.push_back(*q);
			}
		}

}

void write() {
for (list <int>::iterator p=sol.begin();p!=sol.end();p++) 
	fprintf(g,"%d ",*p);
fclose(g);
}

int main() {

read();
solve();
write();

}