백준 1178번 : 간선 추가 - 오일러 경로 , Union&Find 알고리즘

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

1178번: 간선 추가

1. 문제설명

 

주어진 그래프를 오일러 회로 or 오일러 경로로 만드려면

 

몇개의 간선이 추가로 필요한지 구해야 하는 문제입니다.

 

 

---

2. 접근방법[알고리즘]

 

주어진 그래프에서

Union & Find 알고리즘을 이용해

서로 다른 컴포넌트면서 차수가 0이거나 홀수인 노드를 우선 연결해주고

그 이후에도 서로 다른 컴포넌트가 남아있다면

컴포넌트 개수가 1이 될 때까지 모두 연결해준뒤

 

 

한붓그리기가 가능한

오일러 회로나 오일러 경로가 되려면

차수가 홀수인 노드가 최대 2개여야 하므로

 

차수가 홀수인 노드의 개수를 센 다음에

간선을 몇개 더 이어줘야하는지 구하면 답을 구할 수 있습니다.

 

 

 

---

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int v, e, area, ans;
int degree[1001];
int unf[1001];

int Find(int x) {
    if (x == unf[x]) return x;
    else {
        return unf[x] = Find(unf[x]);
    }
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) unf[a] = b;
}


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

    cin >> v >> e;

    for (int i = 1; i <= v; i++) {
        unf[i] = i;
    }


    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;

        degree[a]++;
        degree[b]++;
        Union(a, b);
    }

    //1. 서로 다른 컴포넌트이며 둘 다 차수가 홀 수거나 0이면 이어준다.
    for (int i = 1; i <= v; i++) {
        for (int j = i + 1; j <= v; j++) {
            if ((degree[i] % 2 == 1 || degree[i]==0) && 
                (degree[j] % 2 == 1||degree[j]==0) && 
                (Find(i) != Find(j))) {
                Union(i, j);
                degree[i]++;
                degree[j]++;
                ans++;
            }
        }
    }

    //2. 둘다 차수가 짝수여도 서로 다른 컴포넌트일 경우 서로 이어준다.
    for (int i = 1; i <= v; i++) {
        for (int j = i + 1; j <= v; j++) {
            if (Find(i) != Find(j)) {
                Union(i, j);
                degree[i]++;
                degree[j]++;
                ans++;
            }
        }
    }

    int odd = 0;
    for (int i = 1; i <= v; i++) {
        if (degree[i] % 2 == 1) {
            odd++;
        }
    }


    //3. 차수가 홀 수 인 게 2개이상인 경우 그만큼 연결해주어야한다.
    ans += (odd - 2 > 0) ? ((odd - 2) / 2) : 0;

    cout << ans << '\n';
   
    return 0;
}

백준 1178번 간선 추가