Cod sursa(job #2947472)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 26 noiembrie 2022 09:56:11
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <vector>
#include <queue>

#define MAXN 50000
using namespace std;

struct node{
  int inDegree;
  vector <int> neighbours;
};

queue <int> q;
node graph[MAXN];
int topologicalOrder[MAXN];
int topologicalOrderSize;

void addEdge(int a, int b) {
  graph[a].neighbours.push_back(b);
  graph[b].inDegree++;
}

void makeTopologicalOrder(int n) {
  int i, pos;

  topologicalOrderSize = 0;
  for ( i = 0; i < n; i++ ) {
    if ( !graph[i].inDegree ) {
      q.push(i);
    }
  }

  while ( q.size() ) {
    pos = q.front();
    q.pop();
    topologicalOrder[topologicalOrderSize] = pos;
    topologicalOrderSize++;

    for ( int u : graph[pos].neighbours ) {
      graph[u].inDegree--;
      if ( !graph[u].inDegree ) {
        q.push(u);
      }
    }
  }
}

int main() {
  FILE *fin, *fout;
  fin = fopen("sortaret.in", "r");
  fout = fopen("sortaret.out", "w");

  int n, m, a, b, i;

  fscanf(fin, "%d%d", &n, &m);

  for ( i = 0; i < m; i++ ) {
    fscanf(fin, "%d%d", &a, &b);
    a--;
    b--;

    addEdge(a, b);
  }

  makeTopologicalOrder(n);

  for ( i = 0; i < topologicalOrderSize; i++ ) {
    fprintf(fout, "%d ", topologicalOrder[i] + 1);
  }
  fprintf(fout, "\n");

  fclose(fin);
  fclose(fout);

  return 0;
}