[이산수학] 오일러 순회 구현

그래프 $G$의 오일러 순환(Euler circuit)은 $G$의 모든 모서리를 포함하는 단순 순환이다. $G$의 오일러 경로(Euler path)는 $G$의 모든 모서리를 포함하는 단순 경로이다.

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

#include <algorithm>
#include <iostream>
#include <list>
#include <utility>
#include <vector>

using namespace std;

typedef list<int> li;
typedef vector<li> vli;
typedef vector<int> vi;
typedef vector<vi> vvi;

vvi adjMatrix;
vli adjList;

void sub(int a) {
  while (!adjList[a].empty()) {
    int b = adjList[a].front();
    adjList[a].pop_front();
    if (adjMatrix[a][b] && adjMatrix[b][a]) {
      adjMatrix[a][b]--;
      adjMatrix[b][a]--;
      sub(b);
    }
  }
  cout << a + 1 << ' ';
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  adjMatrix.resize(n, vi(n));
  adjList.resize(n);
  int count;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> count;
      adjMatrix[i][j] = count;
      while (count--) adjList[i].push_back(j);
    }
    if (adjList[i].size() % 2 == 1) {
      cout << "-1\n";
      return (0);
    }
  }
  sub(0);
  return (0);
}