Cod sursa(job #2722362)

Utilizator vladm98Munteanu Vlad vladm98 Data 12 martie 2021 19:44:20
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

vector <pair <int, int>> graph[100005];
int where[100005];
int degree[100005];
int visited[500005];
vector <pair <int, int>> answer;

bool isVisited(int index) {
    return visited[index] != 0;
}

void visit(int index) {
    visited[index] = 1;
}

void dfs(int node) {
    for (int i = where[node]; i < graph[node].size(); ++i) {
        where[node] += 1;
        if (isVisited(graph[node][i].second)) continue;
        visit(graph[node][i].second);
        dfs(graph[node][i].first);
        answer.emplace_back(graph[node][i].first, node);
    }
}

bool visNode[100005];

void dfs2(int node) {
    visNode[node] = true;
    for (auto x : graph[node]) {
        if (!visNode[x.first]) {
            dfs2(x.first);
        }
    }
}

int main() {
    ifstream fin ("ciclueuler.in");
    ofstream fout ("ciclueuler.out");
    ios::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        fin >> x >> y;
        graph[x].emplace_back(y, i);
        graph[y].emplace_back(x, i);
        degree[x] += 1;
        degree[y] += 1;
    }
    dfs2(1);
    for (int i = 1; i <= n; ++i) {
        if (degree[i] % 2 == 1 or !visNode[i]) {
            fout << -1;
            return 0;
        }
    }
    dfs(1);
    for (auto x : answer) {
        fout << x.first << ' ';
    }
    return 0;
}