[1199] 오일러 회로

https://www.acmicpc.net/problem/1199

1199번: 오일러 회로

 

입력은 연결그래프이므로 이쪽은 신경쓰지 않도록 하고, 회로이니 홀수갯수 간선을 갖는 정점이 없어야한다.

이분매칭처럼 작동과정에 비해 코드가 간단하게 구현되는 듯 하다. 아마 DFS를 사용하기 때문이지 싶은데..

 

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

typedef struct {

    int nxt, id;

} state;

stack<state> st[1001];

int n, a[1001][1001];

vector<bool> vst;

void f(int cur) {

    while (1) {

        if (st[cur].empty()) break;

        int id = st[cur].top().id, nxt = st[cur].top().nxt;

        if (vst[id]) {

            st[cur].pop();

            continue;

        }

        vst[id] = true;

        f(nxt);

    }

    cout << cur << ' ';

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n;

    int i, j;

    for (i = 1; i <= n; i++) {

        int cnt = 0;

        for (j = 1; j <= n; j++) {

            cin >> a[i][j];

            cnt += a[i][j];

        }

        if (cnt & 1) {

            cout << "-1";

            return 0;

        }

    }

    int id = 0;

    for (i = 1; i <= n; i++) {

        for (j = 1; j <= i; j++) {

            while (a[i][j]) {

                a[i][j]--;

                id++;

                st[i].push({j, id});

                st[j].push({i, id});

            }

        }

    }

    vst.resize(id + 1);

    f(1);

    return 0;

}

---