Cod sursa(job #1181079)

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

int main () {
    ifstream in;
    in.open("sortaret.in");
    ofstream out;
    out.open("sortaret.out")
    int N, M, i, n1, n2, varf, vecin;
    in >> N >> M;
    vector<int> nodes[N + 1], sortat;
    vector<int>::iterator it;
    stack<int> s;
    int *visited = (int*)calloc(N + 1, sizeof(int));
    for (i = 0; i < N; i++) {
        in >> n1 >> n2;
        if(n1 != n2)
            nodes[n1].push_back(n2);
    }
    s.push(1);
    visited[1] = 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();
        }
    }
    for (it = sortat.begin(); it != sortat.end(); it++)
        g << *it << " ";
    in.close();
    out.close();
    return 0;
}