Cod sursa(job #1249418)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 26 octombrie 2014 23:10:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define Nmax 50100
#define Neighbour Graph[Node][i]

using namespace std;

vector <int> Graph[Nmax];
int N, Index, Order[Nmax];
bool used[Nmax];

void Dfs(int Node) {

    used[Node] = true;

    for(int i = 0; i < Graph[Node].size(); i++)
        if(!used[Neighbour])
            Dfs(Neighbour);

    Order[++Index] = Node;

}
void Solve() {

    for(int i = 1; i <= N; i++)
        if(!used[i])
            Dfs(i);

    reverse(Order + 1, Order + N + 1);

}
void Read() {

    int x, y, M;

    ifstream in("sortaret.in");
    in >> N >> M;

    while(M--) {
        in >> x >> y;
        Graph[x].push_back(y);
        }

    in.close();

}
void Write() {

    ofstream out("sortaret.out");

    for(int i = 1; i <= N; i++)
        out << Order[i] << ' ';

    out << '\n';
    out.close();

}
int main() {

    Read();
    Solve();
    Write();

    return 0;
}