Cod sursa(job #3216042)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 15 martie 2024 16:33:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <vector>

#define MAXN 100010
using namespace std;

struct node{
  bool vis;
  vector <int> neighbours;
};

node graph[MAXN];
vector <int> ans;

void dfs(int pos) {
  graph[pos].vis = true;

  for ( int v : graph[pos].neighbours ) {
    if ( !graph[v].vis ) {
      dfs(v);
    }
  }

  ans.push_back(pos);
}

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

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

  int n, m, i, a, b;

  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 ( !graph[i].vis ) {
      dfs(i);
    }
  }

  for ( i = ans.size() - 1; i >= 0; i-- ) {
    fprintf(fout, "%d ", ans[i]);
  }
  fprintf(fout, "\n");

  fclose(fin);
  fclose(fout);

  return 0;
}