Cod sursa(job #2943107)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 20 noiembrie 2022 16:24:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <vector>
#include <fstream>
#define MAXN 50000

using namespace std;

vector<vector<int>> v;
int inDegree[MAXN], outDegree[MAXN], c[MAXN], f[MAXN];

int main(){
  int n, i, j, m, a, b, dr, st;

  ifstream fin ("sortaret.in");
  fin >> n >> m;
  v.resize(n);

  for(i = 0; i < m; i ++){
    fin >> a >> b;
    a --;
    b --;
    v[a].push_back(b);

    outDegree[a] ++;
    inDegree[b] ++;
  }
  fin.close();

  st = 0;
  dr = 0;
  for(i = 0; i < n; i ++){
    if(inDegree[i] == 0){
      c[dr] = i;
      f[i] = 1;
      dr ++;
    }
  }
  // for(i = 0; i < n; i ++){
  //   printf("%d ", inDegree[i]);
  // }
  // printf("\n");

  while(st < dr){
    int node = c[st];
    st ++;

    for(i = 0; i < v[node].size(); i ++){
      int dest = v[node][i];
      inDegree[dest] --;

      if(!f[dest] && inDegree[dest] == 0){
        c[dr] = dest;
        f[dest] = 1;
        dr ++;
      }
    }
  }

  ofstream fout ("sortaret.out");
  for(i = 0; i < dr; i ++){
    fout << c[i] + 1 << ' ';
  }
  fout.close();
  
  return 0;
}