Cod sursa(job #1812108)

Utilizator taogbta ogb taogb Data 21 noiembrie 2016 20:46:10
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int NMAX = 50000;
vector <int>suc[NMAX + 1];
queue <int>q;
int pred[NMAX];
int main()  {

    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int n, m, x, y;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        pred[y] ++;
        suc[x].push_back(y);
    }

    for(int i = 1; i <= n; i++)
        if(pred[i] == 0)
            q.push(i);

    int current;
    while(!q.empty()) {

        current = q.front();
        for(int i = 0; i < suc[current].size(); i++) {
                pred[suc[current][i]]--;
                if(pred[suc[current][i]] == 0)
                    q.push(suc[current][i]);

        }

        printf("%d ", current);
        q.pop();

    }

    return 0;

}