취미로 코딩하기

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

이번에 볼 문제는 백준 18250번 문제인 철도 여행이다.
문제는 아래 링크를 확인하자.

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

그래프에서의 오일러 경로(Euler path)에 대한 지식을 묻는 문제이다.

어떤 그래프가 연결그래프일 때 이 그래프가 한붓그리기가 가능하려면 각 꼭짓점의 차수(degree)가 전부 짝수이거나 둘이 홀수여야 한다는 사실은 잘 알려져있다.

만약 차수가 홀수인 꼭짓점이 4개, 6개, ... , 2K개 있다면 이 그래프는 최소 몇 번 선을 그려야할까?

답은 간단하다. 한번의 선 긋기로 차수가 홀수인 꼭짓점을 한번에 최대 2개씩 없앨 수 있다는 점을 생각하면 그 답은 금방 알 수 있을 것이다.

이 문제에서는 조건에서 이 그래프가 연결그래프임을 보장해주지 않았음에 유의하자. 즉, 이 문제에서는 연결된 부분그래프 각각에 대해서 이 그래프를 그리기 위해 선을 몇번 그어야 하는지를 세서 모두 더해주는 방식으로 문제를 해결해야한다.

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

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

int deg[200001];
vector<int> G[200001];
bool visited[200001];

int func(int root) {
	vector<int> stk;
	stk.push_back(root);
	visited[root] = 1;

	int cnt = 0;
	while (!stk.empty()) {
		int current = stk.back();
		stk.pop_back();
		if (deg[current] & 1) cnt++;
		for (auto node : G[current]) {
			if (visited[node]) continue;
			visited[node] = 1;
			stk.push_back(node);
		}
	}
	cnt /= 2;
	if (cnt == 0) return 1;
	else return cnt;
}

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

	int N, M; cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
		deg[x]++; deg[y]++;
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (visited[i] || deg[i] == 0) continue;
		ans += func(i);
	}

	cout << ans;
}