Cod sursa(job #1839301)

Utilizator msciSergiu Marin msci Data 2 ianuarie 2017 18:54:05
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

#define SIZE(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()

typedef long long int64; typedef unsigned long long uint64;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;

struct TopologicalSort { // 0 - indexed
    vector<vector<int>>& g;
    vector<bool> visited;
    vector<int> sorted;
    int V, s_ix;
    TopologicalSort(vector<vector<int>>& g) :
            g(g), V(g.size()), s_ix((int) g.size()),
            sorted(g.size(), -1), visited(g.size(), false) {}
    void visit(int u) {
        visited[u] = true;
        for (int v : g[u])
            if (!visited[v]) visit(v);
        sorted[--s_ix] = u;
    }
    void sort() {
        for (int i = 0; i < V; ++i) if (!visited[i]) visit(i);
    }
};

int main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int N, M; scanf("%d %d", &N, &M);
    vector<vector<int>> g(N, vector<int>());
    for (int i = 0; i < M; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        g[x].push_back(y);
    }
    TopologicalSort top(g);
    top.sort();
    vector<int>& ret = top.sorted;
    int num = 0;
    for (int i : ret) {
        if (num++) printf(" ");
        printf("%d", i + 1);
    }
    return 0;
}