BOJ 26155 - 배수관 미스터리 링크
(2024.05.12 기준 G1)

문제

$N$개의 배수구와 두 배수구를 잇는 $M$개의 배수관이 주어진다. 각 배수관은 정상적으로 연결되어 있을 확률 $p$를 가지고 있다.
임계 확률 $p'$가 주어질 때마다, 연결 확률이 $p'$ 이상인 배수관들은 전부 연결된 것으로 가정할 때 연결된 배수구들의 집합 개수 출력

알고리즘

전형적인 분리 집합 + 오프라인 쿼리 문제

풀이

일단 집합의 개수는 분리 집합으로 구할 수 있다. 직간접적으로 연결되지 않은 두 정점이 연결될 때마다 집합의 개수는 하나씩 줄어든다.

이제 주어지는 간선과 질의를 살펴보자. 간선이든 질의든 $p$가 더 높은 것이 우선이 된다.
하나의 간선의 $p_1$, 하나의 질의의 $p_2$가 주어진다고 생각해보자. $p_1 < p_2$이면 질의를 기준으로 간선은 연결되지 않는다. 하지만 $p_1 \ge p_2$이면 질의를 기준으로 간선은 연결된다. 이때, 부등호를 잘 보자. 확률이 같은 경우엔 간선이 우선이 된다.

그러므로 간선과 질의를 모두 모아서 $p$가 내림차순이 되게끔, $p$가 같다면 간선이 우선되게 정렬하자. 그리고 하나씩 훑으면서 간선은 union 시도, 질의는 현재 집합의 개수를 질의의 인덱스에 맞게 저장하면 된다.

코드

• C++

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

typedef tuple<int, float, int, int> query;

const int MAXN = 100'001;

int pa[MAXN];

int find(int u){
    if (pa[u] != u) pa[u] = find(pa[u]);
    return pa[u];
}

bool merge(int u, int v){
    u = find(u); v = find(v);
    if (u < v){
        pa[v] = u;
        return true;
    }
    else if (v < u){
        pa[u] = v;
        return true;
    }
    return false;
}

bool comp(query a, query b){
    if (get<1>(a) == get<1>(b)) return get<0>(a) < get<0>(b);
    return get<1>(a) > get<1>(b);
}

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

    int N, M; cin >> N >> M;

    // 간선과 질의를 한 곳에 담는다.
    vector<query> queries;
    int a, b; float p;
    for (int i = 0; i < M; i++){
        cin >> a >> b >> p;
        queries.push_back({0, p, a, b});
    }

    int Q; cin >> Q;
    for (int i = 0; i < Q; i++){
        cin >> p;
        queries.push_back({1, p, i, i});
    }

    // p가 높을수록 앞선다.
    // 단, p가 같은 간선과 질의가 있다면 간선이 먼저 연결되어야 한다.
    sort(queries.begin(), queries.end(), comp);

    iota(pa + 1, pa + N + 1, 1);
    int res = N, ans[Q];

    for (auto [q, p, a, b]: queries){
        if (q == 0){ // 간선
            if (merge(a, b)) --res; // 연결된다면 집합의 개수는 하나 줄어든다.
        }
        else ans[a] = res; // 질의
    }

    for (int i: ans) cout << i << '\n';
}

• Python

import sys; input = sys.stdin.readline

def find(u):
    if pa[u] != u:
        pa[u] = find(pa[u])
    return pa[u]

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        pa[v] = u
        return True
    elif v < u:
        pa[u] = v
        return True
    return False

N, M = map(int, input().split())

# 간선과 질의를 한 곳에 담는다.
queries = []
for _ in range(M):
    a, b, p = input().split()
    queries.append((0, float(p), int(a), int(b)))

Q = int(input())
for i in range(Q):
    p = float(input())
    queries.append((1, p, i))

# p가 높을수록 앞선다.
# 단, p가 같은 간선과 질의가 있다면 간선이 먼저 연결되어야 한다.
queries.sort(key = lambda x: (-x[1], x[0]))

pa = [i for i in range(N + 1)]
res = N
ans = [0] * Q

for query in queries:
    if query[0] == 0: # 간선
        if union(query[2], query[3]): # 연결된다면 집합의 개수는 하나 줄어든다.
            res -= 1
    else: # 질의
        ans[query[2]] = res

for i in ans:
    print(i)