Cod sursa(job #2667905)

Utilizator raluca1234Tudor Raluca raluca1234 Data 4 noiembrie 2020 01:18:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

struct Graph {
  int n;
  vector<vector<int>> adj;
  Graph(int n_verts) : 
    n(n_verts), adj(n_verts) {}

  vector<int> TopSort() {
    vector<int> in_degree(n, 0);
    for (int from = 0; from < n; from++) {
      for (int to : adj[from]) {
        in_degree[to]++;
      }
    }
    
    vector<int> q;
    for (int node = 0; node < n; node++) {
      if (in_degree[node] == 0) {
        q.push_back(node);
      }
    }

    for (int i = 0; i < (int)q.size(); i++) {
      int node = q[i];

      for (int neighbor : adj[node]) {
        in_degree[neighbor]--;
        if (in_degree[neighbor] == 0) {
          q.push_back(neighbor);
        }
      }
    }

    // if ((int)q.size() < n)
    //   return {};
    return q;
  }

  void AddEdge(int a, int b) {
    adj[a].push_back(b);
  }
};

int main() {
  ifstream fin("sortaret.in");
  ofstream fout("sortaret.out");
  
  int n, m;
  fin >> n >> m;
  
  Graph graph(n);
  
  for (int i = 0; i < m; i++) {
    int x, y;
    fin >> x >> y;
    graph.AddEdge(x - 1, y - 1);
  }

  vector<int> topsort = graph.TopSort();
  for (int node : topsort) {
    fout << node + 1 << " ";
  }
  fout << '\n';

  return 0;
}