Cod sursa(job #2422200)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 17 mai 2019 19:06:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

//ifstream cin("sortaret.in");
//ofstream cout("sortaret.out");

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

vector< vector< int > > g(50005);
vector< int > inv(50005);
vector< int > l;
queue< int > s;

int main() {
    int n, m; //cin >> n >> m;
    fscanf(in, "%d%d", &n, &m);

    int x, y;
    for(int i = 0; i < m; i++) {
        //cin >> x >> y;
        fscanf(in, "%d%d", &x, &y);
        g[x].push_back(y);
        inv[y]++;
    }

    for(int i = 1; i <= n; i++) {
        if(inv[i] == 0) s.push(i);
    }

    while(s.size()) {
        int a = s.front();
        s.pop();
        l.push_back(a);
        for(int i = 0; i < g[a].size(); i++) {
            inv[g[a][i]]--;
            if(inv[g[a][i]] == 0) s.push(g[a][i]);
        }
    }

    for(int i = 0; i < l.size(); i++) {
        //cout << l[i] << " " ;
        fprintf(out, "%d ", l[i]);
    }
}