Cod sursa(job #1890026)

Utilizator savigunFeleaga Dragos-George savigun Data 22 februarie 2017 23:42:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

struct node {
    int val;
    node *next = nullptr;
};

int n, m, ns;
bool viz[50005];
node graph[50005];
int sol[50005];

void add(node *x, int val);
void dfs(node *x);


int main()
{
    int x, y;

    in >> n >> m;

    for (int i = 1; i <= n; ++i) {
        graph[i].val = i;
    }

    for (int i = 1; i <= m; ++i) {
        in >> x >> y;
        add(&graph[y], x);
    }

    for (int i = 1; i <= n; ++i) {
        if (!viz[i]) {
            dfs(&graph[i]);
        }
    }

    /*for (int i = 1; i <= n; ++i) {
        node *x = &graph[i];
        node *y = x -> next;
        out << "Nodul " << i << endl;

        while (y != nullptr) {
            int val = y -> val;
            out << val << ' ';
            y = y -> next;
        }

        out << endl;
    }*/

    for (int i = 1; i <= ns; ++i) {
        out << sol[i] << " ";
    }



    in.close();
    out.close();

    return 0;
}


void dfs(node *x) {
    viz[x -> val] = true;
    node *y = x -> next;

    while (y != nullptr) {
        if (!viz[y -> val]) {
            dfs(&graph[y -> val]);
        }
        y = y -> next;
    }

    sol[++ns] = x -> val;
}



void add(node *x, int val) {

    while (x -> next != nullptr) {
        x = x -> next;
    }

    node *y = new node;
    y -> val = val;
    x -> next = y;
}