Cod sursa(job #3267906)

Utilizator Manolea_Teodor_StefanManolea Teodor Stefan Manolea_Teodor_Stefan Data 12 ianuarie 2025 20:46:56
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>


using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

struct node {
    multiset<int> in;
    multiset<int> out;
};
array<node,100001> g;

stack<int> ans;

stack<int> stk;
void solve(int init) {
    stk.push(init);
    while (!stk.empty()) {
        int x = stk.top();
        node &nodeX = g[x];
        if (!nodeX.out.empty()) {
            int y = *nodeX.out.begin();
            nodeX.out.erase(y);

            node &nodeY = g[y];
            nodeY.in.erase(x);

            stk.push(y);
        } else {
            ans.push(x);
            stk.pop();
        }
    }
}

int n,m;
int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x,y;
        fin >> x >> y;
        g[x].out.insert(y);
        g[y].in.insert(x);
    }

    solve(1);

    while (!ans.empty()) {
        fout << ans.top() << ' ';
        ans.pop();
    }

    return 0;
}