Cod sursa(job #3369423)

Utilizator Andygamer7Negoita Andrei Andygamer7 Data 20 octombrie 2026 11:14:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int main() {
  ifstream fin("sortaret.in");
  ofstream fout("sortaret.out");

  int n, m;
  
  fin >> n >> m;

  vector<vector<int>> graph(n+1);
  vector<int> in_degree(n+1, 0);
  queue<int> q;

  vector<int> sol;

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

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

  while (!q.empty()) {
    int popped = q.front();
    q.pop();
    sol.push_back(popped);
    
    for (int neighbor : graph[popped]) {
      in_degree[neighbor]--;
      if (in_degree[neighbor] == 0) {
        q.push(neighbor);
      }
    }
  }

  for (int node : sol) {
    fout << node << " ";
  }
}