Cod sursa(job #1181114)

Utilizator flore77Simion Florentin flore77 Data 1 mai 2014 20:16:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <stdlib.h>
using namespace std;

void sort_top (int nod, int *&visited, vector<int> &sortat, vector<int> nodes[]) {
    stack<int> s;
    vector<int>::iterator it;
    int varf, vecin;
    s.push(nod);
    visited[nod] = 1;
    while (!s.empty()) {
        varf = s.top();
        vecin = -1;
        for (it = nodes[varf].begin(); it != nodes[varf].end(); it++) {
            if (visited[*it] == 0) {
                vecin = *it;
                break;
            }
        }
        if (vecin != -1) {
            visited[vecin] = 1;
            s.push(vecin);
        }
        else {
            visited[varf] = -1;
            sortat.push_back(varf);
            s.pop();
        }
    }
}

int main () {
    ifstream in;
    in.open("sortaret.in");
    ofstream out;
    out.open("sortaret.out");
    int N, M, i, n1, n2;
    in >> N >> M;
    vector<int> nodes[N + 1], sortat;
    vector<int>::iterator it;
    int *visited = (int*)calloc(N + 1, sizeof(int));
    for (i = 0; i < N; i++) {
        in >> n1 >> n2;
        nodes[n1].push_back(n2);
    }
    for (i = 1; i <= N; i++)
        if (visited[i] == 0)
            sort_top(i,visited,sortat,nodes);
    for (it = sortat.end() - 1; it >= sortat.begin(); it--)
       out << *it << " ";
    in.close();
    out.close();
    return 0;
}