Cod sursa(job #713030)

Utilizator sana1987Laurentiu Dascalu sana1987 Data 14 martie 2012 05:14:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>

using namespace std;

#define MAXN 50001

int N, M;
int u, v;

int indegree[MAXN] = {0, };
int Q[MAXN] = {0, };
vector<int> data[MAXN];


int main(int argc, char **argv)  {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; i++) {
        scanf("%d %d", &u, &v);
        indegree[v]++;
        data[u].push_back(v);
    }

    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0)
            Q[++Q[0]] = i;
    }

    for (int i = 1; i <= N; i++) {
        int x = Q[i];
        for (vector<int>::iterator it = data[x].begin(); it != data[x].end(); it++) {
            indegree[*it]--;
            if (indegree[*it] == 0)
                Q[++Q[0]] = *it;
        }
    }

    for (int i = 1; i <= Q[0]; i++) {
        printf("%d ", Q[i]);
    }

	return 0;
}