백준 16168 : 퍼레이드

 

문제 설명

---

종우는 모든 지점을 거치되, 같은 구간을 두 번 이상 지나지 않는 퍼레이드 경로를 구성하려 한다. 이를 위해 주어진 그래프에서 종우가 원하는 경로를 찾을 수 있는지의 여부를 구하는 문제이다.(V, E ≤ 3,000)

---

 

이 문제는 한붓그리기 문제라는 것을 알 수 있다. 

한붓그리기 즉 오일러 사이클이나 오일러 트레일이 존재하는지를 판단하면 된다.

오일러 사이클 = 모든 정점에서의 간선의 개수가 짝수.

오일러 트레일 = 두 정점에서의 간선의 개수만 홀수(나머지 정점은 모두 짝수여야함).

즉, 모든 정점에서 연결된 간선의 수를 각각 세어 홀수인 지점이 없거나 2개인 경우 해당 조건을 만족한다.

※해당 문제에서 모든 정점이 연결 되어있다는 보장을 하지 않았음으로, 유니온 파인드를 통해 주어진 그래프가 하나의 컴포넌트로 연결 되어있는지 판단해야한다. 이것때문에 틀려서 한참 고민했었다..

---

소스 코드

#include <stdio.h>

int v, e;
int ed[3010];
int par[3010];

int ffind(int x)
{
	if (x == par[x]) return x;
	else return par[x] = ffind(par[x]);
}

void funion(int x, int y)
{
	int a = ffind(x), b = ffind(y);
	if (a < b) par[b] = a;
	else par[a] = b;
}

int main()
{
	int i, j;
	scanf("%d %d", &v, &e);
	for (i = 1; i <= v; i++) par[i] = i;
	for (i = 0; i < e; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		funion(x, y);
		ed[x]++;
		ed[y]++;
	}
	int cnt = 0;
	for (i = 1; i <= v; i++) {
		if (ed[i] % 2 == 1) {
			cnt++;
		}
	}
	for (i = 1; i < v; i++) {
		if (ffind(i) == ffind(i + 1)) continue;
		else {
			printf("NO");
			return 0;
		}
	}
	if (cnt == 2 || cnt == 0) printf("YES");
	else printf("NO");
	return 0;
}