Cod sursa(job #1458050)

Utilizator zvonTutuldunsa Voronokda zvon Data 6 iulie 2015 12:02:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ofstream fo("sortaret.out");
int n;
int t = 0;
int p = 0;

void parcurgere(vector < vector < int > > &v, int k, int c[], int ax[]) {
    //cout << k << "\n";
    int x;
    c[k] = 1;
    while (!v[k].empty()) {
        x = v[k].back();
        v[k].pop_back();
        if (c[x] == 0)
            parcurgere(v, x, c, ax);
    }
    c[k] = 2;
    ax[++p] = k;
    //cout << k << ' ';

}

int main() {
    ifstream fi("sortaret.in");


    int m;
    int i, j;
    int a, b;

    fi >> n >> m;

    int c[n + 1];
    //int d[n + 1];
    //int f[n + 1];
    int parent[n + 1];
    int ax[n + 1];

    vector < vector < int > > v (n + 1);

    for (i = 0; i <= n; i++) {
        c[i] = 0;
        parent[i] = 0;
    }

    for (i = 1; i <= m; i++) {
        fi >> a >> b;
        v[a].push_back(b);
        parent[b] = 1;
    }

    for (i = 1; i <= n; i++)
        if (c[i] == 0 && parent[i] == 0)
            parcurgere(v, i, c, ax);

    for (i = n; i > 0; i--)
        fo << ax[i] << " ";
   /* for (i = 1; i <= n; i++) {
        while (!v[i].empty()) {
            cout << i << " " << v[i].back() << "\n";
            v[i].pop_back();
        }
    } /**/

    fi.close();
    fo.close();
    return 0;
}