Cod sursa(job #2947824)

Utilizator albertaizicAizic Albert albertaizic Data 26 noiembrie 2022 19:17:59
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N=50000;

vector<int> gr[MAX_N],top;
bool marked[MAX_N];
void dfs(int node){
    marked[node]=true;

    for(int nei:gr[node])
      if(!marked[nei])
        dfs(nei);

    top.push_back(node);
}

int main(){
  FILE *fin,*fout;
  int n,m,i,a,b;
  fin=fopen("sortaret.in","r");
  fout=fopen("sortaret.out","w");
  fscanf(fin,"%d%d",&n,&m);

  for(i=0;i<m;i++){
    fscanf(fin,"%d%d",&a,&b);
    a--;
    b--;
    gr[a].push_back(b);
  }


  for(i=0;i<n;i++)
    if(!marked[i])
      dfs(i);

  reverse(top.begin(),top.end());

  for(int node:top)
    fprintf(fout,"%d ", node+1);

  fclose(fin);
  fclose(fout);
  return 0;
}