Cod sursa(job #796645)

Utilizator noctavianNastasie Ion Octavian noctavian Data 11 octombrie 2012 23:36:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void vizit(vector<bool>& viz, vector<int> vizy[], int nod, ofstream& fis) {
    for(int i = 0; i< vizy[nod].size(); i++) 
        if(viz[vizy[nod][i]] == false) {
            viz[vizy[nod][i]] = true;
            vizit(viz, vizy, vizy[nod][i], fis);
            fis << vizy[nod][i] << " ";
        }
}

int main() {
    
    ifstream in("sortaret.in");
    int N, M, n1, n2;
    in >> N >> M;
    vector<int> *x = new vector<int>[N+1];
    vector<int> *y = new vector<int>[N+1];
    vector<bool> viz(N+1, false);

    for(int i = 0; i < M; i++) {
        in >> n1 >> n2;
        x[n1].push_back(n2);
        y[n2].push_back(n1);
    }
    in.close();

    ofstream out("sortaret.out");
    for(int i = 1; i <= N; i++) 
        if(viz[i] == false) {
            viz[i] = true;
            vizit(viz, y, i, out);
            out << i << " ";
        }
    out.close();

    delete [] y;
    delete [] x;

    return 0;
}