Cod sursa(job #1614950)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 26 februarie 2016 12:14:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>

using namespace std;

const int MAX_N = 50000;
const int MAX_M = 100000;
const int NIL = -1;

struct Arc {
    int v;
    int next;
};

Arc G[MAX_M];
int head[MAX_N];
bool color[MAX_N];

int st[MAX_N];
int ss;

void addArc(int u, int v, int pos) {
    G[pos].v = v;
    G[pos].next = head[u];
    head[u] = pos;
}

void DFS(int u) {
    color[u] = 1;

    for (int i = head[u]; i != NIL; i = G[i].next) {
        int v = G[i].v;

        if (!color[v]) {
            DFS(v);
        }
    }
    st[ss++] = u;
}

int main() {
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    fin.tie(0);
    ios_base::sync_with_stdio(false);

    int N, M; fin >> N >> M;

    for (int i = 0; i < N; ++ i) {
        head[i] = NIL;
    }

    for (int i = 0; i < M; ++ i) {
        int u, v; fin >> u >> v;

        addArc(u - 1, v - 1, i);
    }

    for (int i = 0; i < N; ++ i) {
        if (!color[i]) {
            DFS(i);
        }
    }

    while (ss--) {
        fout << 1 + st[ss] << ' ';
    }
    fout << '\n';
    fout.close();

    return 0;
}