Cod sursa(job #1847590)

Utilizator msciSergiu Marin msci Data 14 ianuarie 2017 19:20:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

struct TopoSort { 
  vector< vector<int> >& edges;
  vector<int> sorted;
  vector<bool> visited;
  int V, s_ix;

  TopoSort(vector< vector<int> >& edges) :
    edges(edges), V((int) edges.size()), s_ix((int) edges.size()),
    sorted((int) edges.size(), -1), visited((int) edges.size(), false) {}

  void visit(int u) {
    visited[u] = true;
    for (int v : edges[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> > edges(n, vector<int>());
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    x--, y--;
    edges[x].push_back(y);
  }
  TopoSort topo_sort(edges);
  topo_sort.sort();
  for (int i : topo_sort.sorted) {
    printf("%d ", i + 1);
  }
  puts("");
  return 0;
}