[BOJ] 16168번 퍼레이드 (C++)

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

16168번: 퍼레이드

 

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

int v, e;
vector<int> adj[3001];
int degree[3001];
bool visited[3001];

void dfs(int a){
	visited[a] = true;
	
	for(int i = 0; i < adj[a].size(); i++){
		int n = adj[a][i];
		if(!visited[n])
			dfs(n);
	}
}

int dfsAll(){
	int cnt = 0;
	for(int i = 1; i <= v; i++){
		if(!visited[i]){
			dfs(i);
			cnt++;
		}
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> v >> e;
	for(int i = 0; i < e; i++){
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		degree[a]++;
		degree[b]++;
	}
	
	int component = dfsAll();
	if(component > 1){
		cout << "NO" << endl;
		return 0;
	}
	
	int cnt = 0;
	for(int i = 1; i <= v; i++){
		if(degree[i] % 2 != 0){
			cnt++;
		}
	}
	if(cnt == 0 || cnt == 2) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

 

* 오일러 경로/회로가 존재하는지 판별하는 문제

degree가 홀수인 정점이 2개일 때 오일러 경로가, 0개일 때 오일러 회로가 존재한다.

 

* 임의의 지점에 적어도 하나의 연결 구간이 연결되어 있음이 보장된다.

-> 모든 정점에 간선이 있다는 조건이지, 모든 간선이 하나의 컴포넌트에 포함되어 있다는 조건이 아니다.

-> 그래프의 연결 요소(컴포넌트)의 개수를 세야한다.