간선이 여러개 있을 수있다.
무향 그래프 == 양방향 그래프
adj → 그래프를 표현하는 변수로 사용
오일러 회로의 함정 : 간선이 없다면 정점이 서로 떨어져있어도 오일러 회로가 존재한다.
check 함수 : 모든 정점에 인접한 간선의 수가 짝수인지 확인한다. 이때 두 정점사이의 간선의 수가 0이상 10이하임에 주의 한다. (실수한 부분 : 1이라고 생각함)
makePath 함수 : 오일러 서킷을 만든다. 간단하다. 한 정점에 대해서 DFS를 실행하고, 방문할 수 있는 정점이 없는 경우 해당 정점을 서킷에 push한다.
만약 방향 그래프였을경우 만들어진 서킷을 reverse했어야했다. 또한 들어오는 간선의 수와 나가는 간선의 수가 동일한지 확인했어야한다.
//adj : 그래프 표현
#include <iostream>
#include <vector>
using namespace std;
int N;
/*
오일러 회로인 경우 dfs이용해서 경로생성
*/
vector <int> path;
void makePath(int here, vector<vector<int>>& adj) {
for (int there = 0; there < N; there++) {
if (adj[here][there]) {
adj[here][there]--;
adj[there][here]--;
makePath(there, adj);
}
}
path.push_back(here);
return;
}
/*
오일러 회로인지 아닌지 체크하는 함수.
*/
bool check(vector<vector<int>>& adj) {
for (int y = 0; y < N; y++) {
int eo = 0;
for (int x = 0; x < N; x++)
if (adj[y][x]) eo += adj[y][x];
if (eo % 2)
return false;
}
return true;
}
int main() {
cin >> N;
vector<vector<int>> adj(N, vector<int>(N, 0));
for (int y = 0; y < N; y++)
for (int x = 0; x < N; x++)
cin >> adj[y][x];
if (!check(adj)) {
cout << "-1";
return 0;
}
makePath(0, adj);
for (int v : path)
cout << v + 1 << " ";
}