Cod sursa(job #2928373)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 22 octombrie 2022 20:38:28
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
// Mihai Priboi
// Sunt curios daca merge sa pui un ciclu :))

#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

#define MAXN 100000

int n, m;

vector<int> graph[MAXN];
vector<int> cycle;

bool marked[MAXN];
int inStackPos[MAXN];

bool dfs(int node) {
  marked[node] = true;
  cycle.push_back(node);
  inStackPos[node] = cycle.size();

  for(int neighbour : graph[node]) {
    if(inStackPos[neighbour]) {
      cycle.push_back(neighbour);
      return true;
    }
    else if(!marked[neighbour]) {
      if(dfs(neighbour))
        return true;
    }
  }

  cycle.pop_back();
  inStackPos[node] = 0;
  return false;
}

int main() {
  FILE *fin, *fout;
  int i, x, y;
  bool cycleFound;
  fin = fopen("ciclueuler.in", "r");

  fscanf(fin, "%d%d", &n, &m);
  for(i = 0; i < m; i++) {
    fscanf(fin, "%d%d", &x, &y);
    x--, y--;
    graph[x].push_back(y);
  }

  fclose(fin);

  cycleFound = false;
  i = 0;
  while(i < n && !cycleFound) {
    if(!marked[i])
      cycleFound = dfs(i);

    i++;
  }

  fout = fopen("ciclueuler.out", "w");

  if(cycle.empty())
    fprintf(fout, "-1");
  else
    for(i = inStackPos[cycle.back()] - 1; i < cycle.size(); i++)
      fprintf(fout, "%d ", cycle[i] + 1);

  fclose(fout);
  return 0;
}