백준(BOJ) 16168 퍼레이드 **

# 한붓 그리기 # DFS # 스까묵자

한붓 그리기 : 노드에 연결된 경로의 갯수가 홀수인 노드가 0개 또는 2개일 때 한붓 그리기가 가능하다.

# 실수 했던 점

주어진 모든 노드가 연결되지 않았을 때의 경우를 생각하지 못했다.

#include<iostream>
#include<cstdio>
#include<vector>
#include <deque>
#include <string.h>
#include <algorithm>
using namespace std;
long long ans;

int n, m, arr[3005];
bool visit[3005];
vector<int> v[3005];

void dfs(int cur)
{
	if (visit[cur])
		return;
	visit[cur] = true;

	for (int i = 0; i < v[cur].size(); i++)
	{
		arr[cur]++;
		dfs(v[cur][i]);
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	int a, b;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int num = 0, ans=0;
	for (int i = 1; i <= n; i++)
	{

		if (!visit[i])
		{
			num++;
			fill_n(&arr[0], 3005, 0);
			dfs(i);
			for (int i = 1; i <= n; i++)
				if (arr[i] % 2 == 1)
					ans++;

		}
	}
	if (num == 1 && (ans == 0 || ans == 2))
		printf("YES");
	else
		printf("NO");
	return 0;
}