[BOJ 16168 // C++] 퍼레이드

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16168번 문제인 퍼레이드이다.
문제는 아래 링크를 확인하자.

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

16168번: 퍼레이드

문제의 조건을 만족하는 경로는 오일러 경로임을 관찰하자.

 

주어진 그래프가 오일러 경로를 가지기 위한 필요충분조건은 해당 그래프가 연결그래프이며 차수가 홀수인 노드가 2개 이하(2개 또는 0)임과 같다는 점을 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, E;
vector<int> G[3001];
bool visited[3001];

void dfs(int cur) {
	visited[cur] = 1;
	for (auto& node : G[cur]) {
		if (visited[node]) continue;
		dfs(node);
	}
}

int oddcnt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> E;
	while (E--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	dfs(1);
	for (int i = 1; i <= N; i++) {
		if (G[i].size() & 1) oddcnt++;
		if (!visited[i]) {
			cout << "NO";
			return 0;
		}
	}

	if (oddcnt > 2) cout << "NO";
	else cout << "YES";
}