Mai intai trebuie sa te autentifici.

Cod sursa(job #1884424)

Utilizator preda.andreiPreda Andrei preda.andrei Data 18 februarie 2017 19:00:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>

using namespace std;

struct Node
{
    bool visited = false;
    vector<int> edges;
};

using Graph = vector<Node>;

void Dfs(Graph &g, int node, vector<int> &ord, int &ord_ind)
{
    g[node].visited = true;
    for (int i : g[node].edges) {
        if (!g[i].visited) {
            Dfs(g, i, ord, ord_ind);
        }
    }
    ord[ord_ind++] = node;
}

int main()
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int n, m;
    fin >> n >> m;

    Graph graph(n);
    while (m--) {
        int x, y;
        fin >> x >> y;
        graph[y - 1].edges.push_back(x - 1);
    }

    vector<int> order(n);
    int order_index = 0;

    for (int i = 0; i < n; ++i) {
        if (!graph[i].visited) {
            Dfs(graph, i, order, order_index);
        }
    }

    for (int i : order) {
        fout << i + 1 << " ";
    }
    return 0;
}