Codeforces Round #738 (Div. 2)-D1. Mocha and Diana (Easy Version)

문제 설명

그래프이론에서 숲이란 사이클이 없는 무뱡향 그래프 이다. 이때 모든 노드와 연결될 필요 없다.

노원구에 사는 동환과 영준은 서로 친구이다. 이들은 모두 재벌이라서 각자 $1$부터 $n$까지 번호가 붙여있는 노드가 있는 숲을 가지고있다. 그리고 이들은 숲에 간선을 다음과 같은 방식으로 추가하는 것을 즐긴다.

• 간선을 추가하고 두 숲 모두 여전히 숲을 유지해야한다.
• 두 숲 모두 같은 간선을 추가해야 한다. 즉 간선 $(u,v)$를 동환이의 숲에 추가한다면 동일한 간선 $(u,v)$를 영준이에 숲에 추가해야하고 이 반대의 경우도 성립한다.

동환이와 영준이는 연결 할 수 있는 최대한 많은 간선을 연결하고 싶어한다.

Input
첫번째 줄에는 각각 노드의 수, 동환이의 숲에 있는 초기 간선의 수, 영준이의 숲에 있는 초기 간선의 수를 나타내는 정수 $n,m_1,m_2(1\le n\le 1000,0\le m_1,m_2<n)$이 주어진다.

다음 $m_1$개의 줄에는 동환이의 숲에 있는 간선의 정보를 나타내는 두 정수 $n$과 $v(1\le u,v\le n,u\ne v)$ 가 주어진다.

다음 $m_2$개의 줄에는 동환이의 숲에 있는 간선의 정보를 나타내는 두 정수 $n$과 $v(1\le u,v\le n,u\ne v)$ 가 주어진다.

Output
첫번째 줄에는 동환이와 영준이가 최대로 추가할 수 있는 간선의 수 $h$를 출력한다.

다음 $h$개의 줄에는 둘이 추가한 간선의 정보를 나타내는 두 정수 $u$와 $v(1\le u,v\le n,u\ne v)$ 를 출력한다.

Example
input
8 1 2
1 7
2 6
1 5

output
5
5 2
2 3
3 4
4 7
6 8

문제 접근

사용한 알고리즘: 그래프, DSU, 구성적 알고리즘, 완전탐색
걸린 시간 : 00:08
그냥 Disjoint-set union 자료구조을 이용하면 풀리는 문제이다. 대회에서 이거 풀기까지 4050분 정도 남았는데, 그냥 A번 풀지말고 이 문제 풀걸 그랬다. 그랬으면 14001500대 퍼포먼스가 찍혔을 것 같은데 아쉽다.

분리집합 자료구조는 이해하기 쉬우면서 그래프를 비롯한 다양한 알고리즘 문제에 사용되기 때문에 반드시 알아두고 STL에 없기 때문에 구현할 줄 알아한다.

사이클을 판별하는 방법은 두 노드의 부모가 같으면 사이클이라고 판별하면 된다. 그리고 노드의 부모를 찾는 함수는 find에 정의해 놓았다. $n$의 제한이 1000밖에 안되기 때문에 그냥 완전 탐색을 돌려서 모든 간선을 다 따져보는것이 속 편하다.

정답 코드

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

typedef struct _forest{
    vector<int> root;

    _forest(int n) : root(n + 1){
        for(int i = 1; i <= n; i++) root[i] = i;
    }

    int find(int n){
        if(root[n] == n) return n;
        return root[n] = find(root[n]);
    }

    bool merge(int u, int v){
        u = find(u);
        v = find(v);

        if(u == v) return false;
        root[u] = v;
        return true;
    }
}forest;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int n, a, b; cin >> n >> a >> b;
    forest f1(n), f2(n);
    while(a--){
        int x, y; cin >> x >> y;
        f1.merge(x, y);
    }
    while(b--){
        int x, y; cin >> x >> y;
        f2.merge(x, y);
    }

    vector<pair<int, int>> ans;
    for(int i = 1; i < n; i++){
        for(int j = i + 1; j <= n; j++){
            if(f1.find(i) != f1.find(j)){
                if(f2.merge(i, j)){
                    f1.merge(i, j);
                    ans.push_back({i, j});
                }
            }
        }
    }

    cout << ans.size() << "\n";
    for(auto x : ans) cout << x.first << " " << x.second << "\n";
    return 0;
}