Cod sursa(job #2379504)

Utilizator mihaidanielmihai daniel mihaidaniel Data 13 martie 2019 19:02:36
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct Node
{
    int info;
    Node *next;
    Node (int inf = 0, Node* nxt = NULL) {info = inf; next = nxt;}
};
Node *p = NULL, *q;
vector <vector <int> > mat;
vector <int> v;

void DFS (int x) {
    v[x] = 1;
    int n = mat[x].size();
    for (int i = 0; i < n; ++i) {
        if (!v[mat[x][i]]) {DFS(mat[x][i]);}
    }
    p = new Node (x, p);
}

int main()
{
    ifstream in ("sortaret.in");
    ofstream out ("sortaret.out");
    int n, m, x, y, i;
    in >> n >> m;
    mat.resize (n+1);
    v.resize (n+1, 0);

    for (i = 0; i < m; ++i) {
        in >> x >> y;
        mat[x].push_back (y);
    }

    for (i = 1; i <=n; ++i) {
        if (!v[i]) {DFS(i);}
    }

    while (p) {
        out << " " << p->info;
        q = p;
        p = p->next;
        delete q;
    }
    return 0;
}