Cod sursa(job #2326134)

Utilizator razviii237Uzum Razvan razviii237 Data 23 ianuarie 2019 12:49:58
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

const int maxn = 5e4+5;
vector <int> nod[maxn];
int n, m, i, a, b, v[maxn], is[maxn];

void add(int a, int b) {
    nod[a].push_back(b);
}

typedef struct nd
{
    int i;
    nd *nxt;
} *pnod;

pnod ans;

void puttop(int x) {
    pnod dn = new nd;
    dn -> i = x;
    dn -> nxt = ans;
    ans = dn;
}

void dfs(int x) {

    if(v[x] == 1 || v[x] == 2) {
        return;
    }
    v[x] = 2;
    for(auto u : nod[x]) {
        if(v[u] == 0) {
            dfs(u);
        }
    }
    v[x] = 1;
    puttop(x);
}

void sortaret() {
    for(int i = 1; i <= n; i ++) {
        if(v[i] == 0) {
            dfs(i);
        }
    }
}

int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i ++) {
        f >> a >> b;
        add(a, b);
    }

    for(i = 1; i <= n; i ++) {
        puttop(i);
    }

    sortaret();

    for(pnod j = ans; j != NULL; j = j -> nxt) {
        if(is[j -> i] == false) {
            is[j -> i] = true;
            g << (j -> i) << ' ';
        }
    }

    f.close();
    g.close();
    return 0;
}