백준 소스코드 [C++] 1199 오일러 회로

www.acmicpc.net/problem/1199

1199번: 오일러 회로

백준 소스코드 [C++] 1199 오일러 회로

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <deque>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#include <cassert>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pli pair<ll, int>
#define make_unique(v) sort(all(v)), v.erase(unique(all(v)), v.end())
typedef long long ll;
using namespace std;

struct Edge {
    int next, id;
};

vector<vector<Edge>> adj;
vector<int> chk;

void dfs(int here){
    while (true) {
        while(!adj[here].empty() && chk[adj[here].back().id]) adj[here].pop_back();
        if(adj[here].empty()) break;
        Edge edge = adj[here].back();
        adj[here].pop_back();
        chk[edge.id] = true;
        dfs(edge.next);
    }
    cout<<here<<" ";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, id=0, edge;
    cin>>n;
    adj.resize(n+1);
    bool valid = true;
    for(int i=1;i<=n;i++){
        int sum = 0;
        for(int j=1;j<=n;j++){
            cin>>edge;
            sum +=edge;
            if (i<j && edge) {
                while(edge) {
                    edge--;
                    adj[i].push_back(Edge{j, id});
                    adj[j].push_back(Edge{i, id});
                    id++;
                }
            }
        }
        if (sum % 2 == 1) valid = false;
    }
    chk.resize(id + 1, false);
    if (!valid) printf("-1");
    else dfs(1);
    return 0;
}