Cod sursa(job #2943094)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 20 noiembrie 2022 16:15:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 50000

vector <int> graf[MAXN];
int sol[MAXN];
bool marked[MAXN];

void DFS(int nod, int &ind){
  int i;
  marked[nod] = true;
  for(i = 0; i < graf[nod].size(); i++){
    if(marked[graf[nod][i]] == false){
      DFS(graf[nod][i], ind);
    }
  }
  sol[ind] = nod;
  ind++;
}

int main()
{
    FILE *fin, *fout;
    int n, m, i, a, b, ind;
    fin = fopen("sortaret.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i = 0; i < m; i++){
      fscanf(fin, "%d%d", &a, &b);
      graf[a - 1].push_back(b - 1);
    }
    fclose(fin);
    ind = 0;
    for(i = 0; i < n; i++){
      if(marked[i] == false){
        DFS(i, ind);
      }
    }
    fout = fopen("sortaret.out", "w");
    for(ind = ind - 1; 0 <= ind; ind--){
      fprintf(fout, "%d ", sol[ind] + 1);
    }
    fclose(fout);
    return 0;
}