[백준 21043번] [오일러 경로] Domino Line

꼬리에 꼬리를 무는 형태이므로, 오일러 경로를 의심해 볼 수 있다.

 

동일한 컴포넌트 안에서 해당 정점과 연결된 간선이 홀수인 정점의 개수가 2k이면, 한붓그리기로 최소 k개의 경로로 만들 수 있음은 오일러 경로의 증명을 통해 논증할 수 있다.

다만, 오일러 회로의 경우, 해당 점점과 연결된 간선이 홀수인 정점의 개수가 0개임에도 불구하고 최소 1개의 경로로 만들 수 있으므로 예외처리 해야 한다. 즉, 해당 컴포넌트에서 최소경로는 max(해당 점점과 연결된 간선이 홀수인 정점의 개수 / 2, 1)이다.

또한 다른 컴포넌트간에는 따로 따져서 최소값끼리의 덧셈을 통해 구해주면 된다.

 

추가적으로 동일한 컴포넌트에 위치하고 있는지는 dfs와 visited배열을 활용해서 처리해주면 된다.

 

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;
vector<int> visited(50001, -1);
vector<int> edge[50001];

int dfs(int edge_val){
    if(visited[edge_val]) return 0;
    else{
        visited[edge_val] = 1; 
        int odd_num = 0;
        if(edge[edge_val].size() % 2 == 1) odd_num++;
        for(int i = 0; i < edge[edge_val].size(); i++){
            odd_num += dfs(edge[edge_val][i]);
        }
        return odd_num;
    }
}

int main(void){
    fastio;
    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        int t1, t2;
        cin >> t1 >> t2;
        edge[t1].push_back(t2);
        edge[t2].push_back(t1);
        visited[t1] = 0;
        visited[t2] = 0;
    }

    int min_paint = 0;
    for(int i = 1; i <= 50000; i++){
        if(visited[i] == 0){
            min_paint += max(dfs(i) / 2, 1);
        }
        else continue;
    }

    cout << min_paint << "\n";
    return 0;
}