[C++] 백준 BOJ 1717 집합의 표현 (시간초과 해결)

문제링크 : https://boj.kr/1717

시간 제한을 신경써야 하는 문제로 iostream의 std::cin을 쓸 경우 시간 초과가 난다.

scanf를 사용하거나 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);  를 같이 사용해야 한다.

std::endl 도 마찬가지로 시간이 오래 걸리는 키워드로 "\n"을 써주는 편이 훨씬 빠르다고 한다.

그래프 문제로 처음엔 서로소 집합으로 자기 자신을 참조하는 형태로 노드를 표현한다.

연산이 될 때마다 루트노드를 업데이트 시킨다.

int find(int node) {

    if (root[node] == node)

        return node;

    else

        return find(root[node]);

}

위의 경우 find(5)을 했을 경우 예시로 5 -> 7 -> 3->2->1 와 같은 경우로 탐색을 할 수 있기 때문에 시간이 오래 걸린다.

5 -> 7 -> 3 -> 2 - > 1 이라던지 8 -> 6 -> 1 같은 경우도 어짜피 모든 경로의 값들이 1로 향한다면 같은 집합에 속한다고 볼 수 있다.

따라서, root[5] = root[7] = root[3] = root[2] = root[1] 이런식으로 해주면 되므로 루트노드까지의 탐색이 완료되면 해당 노드의 루트노드를 갱신시켜주면 된다.

return 값을 return root[node] = find(root[node]); 로 해주면 return 될 때 마지막의 루트노드 값이 참조했던 모든 노드들에 업데이트 된다.

#include <cstdio>
#include <vector>
using namespace std;
 
vector<int>root;
 
int find(int node) {
    if (root[node] == node)
        return node;
    else
        return root[node] = find(root[node]);
}
 
void uni(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    root[pb] = pa;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    int num, calc;
    scanf("%d %d", &num, &calc);
    //cin >> num >> calc;
 
    for (int i = 0; i <= num; i++)
        root.push_back(i);
 
    int cmd, a, b;
    for (int i = 0; i < calc; i++) {
        scanf("%d %d %d", &cmd, &a, &b);
        //cin >> cmd >> a >> b;
        if (cmd == 0) {
            uni(a, b);
        }
        else {
            if (find(a) == find(b))
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    
    return 0;
}

또는

#include <iostream>
#include <vector>
using namespace std;
 
vector<int>root;
 
int find(int node) {
    if (root[node] == node)
        return node;
    else
        return root[node] = find(root[node]);
}
 
void uni(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    root[pb] = pa;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    int num, calc;
    cin >> num >> calc;
 
    for (int i = 0; i <= num; i++)
        root.push_back(i);
 
    int cmd, a, b;
    for (int i = 0; i < calc; i++) {
        cin >> cmd >> a >> b;
        if (cmd == 0) {
            uni(a, b);
        }
        else {
            if (find(a) == find(b))
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
    
    return 0;
}