BOJ 1199 - 오일러 회로

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

양방향그래프 오일러서킷 코드기록용

 

<문제설명>

오일러서킷 존재하면 출력, 없으면 -1출력

 

<풀이>

오일러트레일은 무시해야 함. ->차수가 홀수인 정점이 없으면 오일러서킷 존재함

 

<코드>

int adj[MAX][MAX], n, deg[MAX];
bool odd;
vector<int> ans;
void euler(int u) {
	for (int v = 0; v < n; v++) {
		while (adj[u][v] > 0) {
			adj[u][v]--;
			adj[v][u]--;
			euler(v);
		}
	}
	ans.push_back(u);
}

int main() {
	FAST;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> adj[i][j];
			deg[i] += adj[i][j];
		}
		if (deg[i] % 2) odd = true;
	}

	if (odd) 
		cout << -1 << '\n';
	else {
		for (int i = 0; i < n; i++) if (deg[i]) {
			euler(i);
			break;
		}

		for (int i : ans)
			cout << i + 1 << " ";
		cout << '\n';
	}	
}