[백준 18250] 철도 여행

오일러 경로로도 풀 수 있다고는 하지만 학습하지 않았기 때문에 간단 관찰을 통해 풀어보고자 한다.

1. 관찰

먼저 어떤 Trail 있다고 치자. 이때 각 정점의 차수를 확인하면 시작점과 끝점은 \(1\)개이고, 나머지는 \(2\)개이다.

이 점을 통해서 한가지 사실을 관찰할 수 있다. 어떤 Trail의 시작점은 홀수 차수를 가진 정점에서 시작하고, 홀수 차수를 가진 정점에서 끝난다. 라는 사실을 알 수 있다. 하지만 사이클인 그래프에서는 적용되지 않는다.

 

왜 그런지 이유를 생각해보자. 사이클이 아니라면 처음에 홀수 차수를 가진 정점이 \(2\)개이상이 있을 것이다. 그 정점 중 아무거나 집어서 Trail을 만들어 제거하자.

그렇다면 시작점과 끝점이 아닌 부분은 \(2\)개씩 지어진다. 만약 그 사이에 홀수 차수가 있더라도 홀수 차수가 유지된다는 소리이다.

 

그렇기 때문에 홀수 차수끼리 시작과 끝을 정해서 Trail을 만들게 되면 또 홀수차수가 존재하고,

결국에는 답은 \((홀수차수정점의개수)/2\)가 된다.

 

사이클인 경우에는 그냥 \(1\)번으로 처리해주면 된다.

2.소스 코드

#include <bits/stdc++.h>


using namespace std;


vector<int> V[200001];
bitset<200001> go, visit;


int dfs(int now) {
    visit[now] = true;
    int cnt = (V[now].size() % 2);


    for (int w : V[now]) {
        if (visit[w]) continue;
        cnt += dfs(w);
    }


    return cnt;
}


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


    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        go[u] = go[v] = true;
        V[u].push_back(v);
        V[v].push_back(u);
    }


    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (visit[i] || !go[i]) continue;
        int cnt = dfs(i);
        if (cnt == 0) ans++;
        else ans += cnt / 2;
    }


    cout << ans;
    return 0;
}