Cod sursa(job #2938562)

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


using namespace std;

void dfs(int nod, const vector<vector<int> > &graph, vector<int>& in_degree,vector<int> &ans){
  ans.push_back(nod);
  for(auto it:graph[nod]){
    in_degree[it] --;
  }

  for(auto it:graph[nod]){
    if(in_degree[it] == 0){
      dfs(it, graph, in_degree, ans);
    }
  }
}

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);
      }
    }
  }
*/

  vector<int> roots;
  vector<int> ans;
  for(int i = 1;i <= n;i++){
    if(in_degree[i] == 0){
      roots.push_back(i);
    }
  }

  for(auto it:roots){
    dfs(it, graph, in_degree, ans);
  }

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

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