Cod sursa(job #2938554)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 12 noiembrie 2022 11:15:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>


using namespace std;

int main(){
  ifstream f("sortaret.in");
  ofstream g("sortaret.out");

  int n, m;
  f >> n >> m;
  vector<vector<int> > graph(n + 1, vector<int>());
  vector<int> in_degree(n + 1, 0);


  for(int i = 1;i <= m;i++){
    int x, y;
    f >> x >> y;
    graph[x].push_back(y);
    in_degree[y] ++;
  }

  queue<int> q;

  for(int i = 1;i <= n;i++){
    if(in_degree[i] == 0){
      q.push(i);
    }
  }

  vector<int> ans;

  while(!q.empty()){
    int nod = q.front();
    q.pop();
    ans.push_back(nod);

    for(auto it:graph[nod]){
      in_degree[it]--;
      if(in_degree[it] == 0){
        q.push(it);
      }
    }
  }

  if((int)ans.size() != n){
    assert(false); 
  }

  for(auto it:ans){
    g << it << " ";
  }
  return 0;
}