Cod sursa(job #554490)

Utilizator sodamngoodSo Damn Good sodamngood Data 14 martie 2011 21:29:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define maxn 50010

int N, M;
int deg[maxn], Q[maxn];
vector<int> G[maxn];

int main() {
    FILE *f1=fopen("sortaret.in", "r"), *f2=fopen("sortaret.out", "w");
    int i, j, x, y;

    fscanf(f1, "%d %d\n", &N, &M);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d\n", &x, &y);
         G[x].push_back(y);
         deg[y] ++;
    }

    for(i=1; i<=N; i++) {
         if(deg[i] == 0) {
              //bag in coada
              Q[0] ++; Q[ Q[0] ] = i;
         }
    }

    for(i=1; i<=N; i++) {
         int nod = Q[i];
         for(j=0; j<G[nod].size(); j++) {
              deg[ G[nod][j] ] --;
              if(deg[ G[nod][j] ] == 0) {
                   //bag in coada
                   Q[0] ++;
                   Q[ Q[0] ] = G[nod][j];
              }
         }
    }

    for(i=1; i<=N; i++) {
         fprintf(f2, "%d ", Q[i]);
    } fprintf(f2, "\n");

    fclose(f1); fclose(f2);
    return 0;
}