Cod sursa(job #1241009)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 12 octombrie 2014 14:30:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>

using namespace std;

vector<int> graf[300000];

int n, m, in[200000], out[200000], sol[300000];

int timp = 0;

void df(int nod) {
    in[nod] = ++timp;
    for(vector<int> :: iterator it = graf[nod].begin(); it < graf[nod].end(); it ++ ) {
        if (in[*it] == 0) {
            df(*it);
        }
    }
    out[nod] = ++ timp;
    sol[timp] = nod;
}

void solve() {
    for (int i = 1; i <= n ; i++) {
        if (in[i] == 0){
            df(i);
        }
    }
}

void afisare() {
    ofstream g("sortaret.out");
    for (int i = 2*n; i >0; i --) {
        if (sol[i] != 0) {
            g << sol[i] << ' ';
        }
    }
    g.close();
}

void citire() {
    ifstream f("sortaret.in");
    f>> n >> m ;
    int x, y;
    for ( int i = 1 ; i <= m ; i++) {
        f >> x >>y;
        graf[x].push_back(y);
    }
    f.close();
}

int main()
{
    citire();
    solve();
    afisare();
}