Cod sursa(job #1925507)

Utilizator Mstar_AngelComan Mara Stefania Mstar_Angel Data 13 martie 2017 12:11:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
//Sortare topologica
// DFS : se coboara pana nu mai exista succesor, si punem nodul in ordine inversa
#include<stdio.h>
#include<vector>
#define N 50001
using namespace std;
vector <int> v[N];
int viz[N];
int sol[N];
int k;

void dfs (int nod){
  int i;
  viz[nod] = 1;
  for (i=0;i<v[nod].size();i++)
    if (viz[v[nod][i]] == 0)
      dfs (v[nod][i]);
  sol[++k] = nod;
}

int main (){
  FILE *in, *out;
  in = fopen ("sortaret.in","r");
  out = fopen ("sortaret.out","w");
  int n,m,i,n1,n2;
  fscanf(in,"%d%d",&n,&m);
  for (i=1;i<=m;i++){
    fscanf(in,"%d%d",&n1,&n2);
    v[n1].push_back(n2);
  }

  for (i=1;i<=n;i++)
    if (viz[i] == 0)
      dfs (i);

  for (i=n;i>=1;i--)
    fprintf (out,"%d ",sol[i]);


  fclose (in);
  fclose (out);
  return 0;
}