Cod sursa(job #2644632)

Utilizator anabatAna Batrineanu anabat Data 25 august 2020 12:10:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>

using namespace std;

#define MMAX 100000
#define NMAX 50000

#include <vector>
#include <queue>

vector <int> g[MMAX+1];
vector <int> rez;
int viz[NMAX+1];

void dfs(int nod){
  viz[nod]=1;
  for(auto next : g[nod]){
    if(viz[next]!=1){
      dfs(next);
    }
  }
  viz[nod]=1;
  for(auto next : g[nod]){ ///verificam daca toti vecinii sunt scosi
    if(viz[next]!=1){
      viz[next]=1;
    }
  }
  rez.push_back(nod);
}

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);
    g[a].push_back(b);
  }
  for(i=1;i<=n;i++){
    if(viz[i]!=1){
      dfs(i);
    }
  }
  for(i=rez.size()-1;i>=0;i--){
    fprintf(fout,"%d ",rez[i]);
  }

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