Cod sursa(job #669160)

Utilizator KoniacDocea Andrei Koniac Data 26 ianuarie 2012 11:13:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

FILE * f = fopen("sortaret.in","r");
FILE * g = fopen("sortaret.out","w");

int n,m,now,x,y;
int pred[50001];

vector<int> L[50001];
queue<int> Q;

int main(){
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++){
		fscanf(f,"%d%d",&x,&y);
		L[x].push_back(y);
		pred[y]++;
	}
    for(int i=1;i<=n;i++)
        if(pred[i]==0)
            Q.push(i);
    while(!Q.empty()){
        now = Q.front();
        fprintf(g,"%d ",now);
        for(vector<int> :: iterator it = L[now].begin() ; it != L[now].end(); it ++){
			pred[*it]--;
			if(pred[*it] == 0){
				Q.push(*it);
			}
		}
        Q.pop();
    }
	
	fclose(f);
	fclose(g);
    return 0;
}