Cod sursa(job #2797215)

Utilizator Antonia_onisoruantonia onisoru Antonia_onisoru Data 9 noiembrie 2021 15:57:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>

using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

const int MAXN = 50000;
int n;

int v[MAXN + 1];
int size_v;

struct nod{
  vector<int> next;
  bool vizitat;
};

nod noduri[MAXN + 1];

void read_graph(){
  int m, i, x, y;
  in>>n>>m;

  for( i = 0; i < m; i++ ){
    in>>x>>y;
    noduri[x].next.push_back(y);
  }
}

void dfs(int index){

  noduri[index].vizitat = 1;
  //cout<<index + 1<<'\n';

  for(int i = 0; i < noduri[index].next.size(); i++ ){
    //cout<<noduri[noduri[index].next[i]].vizitat<<" "<<noduri[index].next[i] + 1<<" "<<noduri[noduri[index].next[i]].vizitat<<'\n';
    if( noduri[noduri[index].next[i]].vizitat == 0){
      dfs(noduri[index].next[i]);
    }
  }
  v[size_v] = index;
  size_v++;
}

int main()
{
    int cnt, i;
    read_graph();

    cnt = 0;
    size_v = 0;
    for( i = 1; i <= n; i++ ){
      //cout<<noduri[i].vizitat<<'\n';
      if( noduri[i].vizitat == 0 ){
        dfs(i);
      }
    }
    for( i = size_v - 1; i >= 0; i-- )
      out<<v[i]<<" ";
    return 0;
}