Cod sursa(job #2906209)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 25 mai 2022 09:07:55
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <vector>

#define MAXN 50000
using namespace std;

FILE *fin, *fout;

struct node{
  bool visited;
  int nrEdgesToNode;
  vector <int> edges;
};

node tree[MAXN + 1];
int v[MAXN + 1];
int ans[MAXN + 1];
int vSize, ansSize;

void addEdge(int a, int b) {
  tree[a].edges.push_back(b);
  tree[b].nrEdgesToNode++;
}

void dfs(int pos) {
  tree[pos].visited = true;

  for ( int i : tree[pos].edges ) {
    fprintf(fout, "%d ", i);
    if ( !tree[i].visited )
      dfs(i);
  }
}

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

  int n, m, i, a, b, nod;

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

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

    addEdge(a, b);
  }

  for ( i = 1; i <= n; i++ ) {
    if ( !tree[i].nrEdgesToNode ) {
      v[vSize] = i;
      vSize++;
    }
  }

  while ( vSize ) {
    vSize--;
    nod = v[vSize];
    ans[ansSize] = nod;
    ansSize++;
    for ( int j : tree[nod].edges ) {
      tree[j].nrEdgesToNode--;
      if ( !tree[j].nrEdgesToNode ) {
        v[vSize] = j;
        vSize++;
      }
    }

    tree[nod].edges.clear();
  }

  for ( i = 0; i < ansSize; i++ ) {
    fprintf(fout, "%d ", ans[i]);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}