Pagini recente » Cod sursa (job #2035953) | Cod sursa (job #2568902) | Cod sursa (job #2928373)
// 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;
}