Hackerrank) Jim and his LAN Party

문제 링크

\(1\le{N, M}\le{10^5}\)

\(0\le{Q}\le{10^5}\)

이 문제는 N개의 노드가 있고, 각 노드는 M개의 그룹중 하나에 속한다. 그리고 총 Q개의 간선을 설치할건데

1번부터 순차적으로 설치할것이다. 그럴 때에 각 그룹에 대해 그룹에 속한 노드들이 모두 하나의 컴포넌트로

연결되는 최소 간선 번호를 구하는것이다. 그러므로 최종적으로 M개의 정수를 출력하면된다.

Q번 간선까지 설치했는데도 모든 그룹 노드들이 연결되지않는다면 -1을 출력, 그리고 하나도 간선을 설치하지

않아도 모두 연결되면 0을 출력하면된다. 일단 0을 출력하는 경우는 그룹에 속한 노드가 딱 하나만

있는 경우밖에 없다. 그러므로 이경우만 따로 처리해주면 될 것이다. 

일단 naive 하게 생각해보자. M개의 그룹에 대해서 Q개의 에지를 차례대로 연결해보면서

몇번 에지를 연결하는 순간 모두 연결되는지 판별해보자. 유니온파인드를 하면서

cnt[i] : i번 disjoint-set 에 속한 그룹 m 에 속한 노드의 개수

를 저장하면서 merge 할 때마다 합치면서 현재 시점에서 그룹 k에 속한 아무 노드

하나만 기억하고있다가 cnt[find(그 아무 노드)] 가 전체 그룹에 속한 노드수와 같은지 보는식으로하면

O(M(N + Q)) 에 구할 수 있을 것이다.(N은 초기화하는데 걸리는 시간)

그런데 이러면 너무 느리다. 그래서 패러럴 바이너리 서치(parallel binary search)를 써야한다.

패러럴 바이너리 서치에 대한 자세한 설명은 생략하고

미리 각 그룹마다 해당 그룹에 속한 노드들을 저장해두면 그 노드들이 같은 set에 속하는지만

모든 그룹에 대해 확인해주는 식으로하면 반복문 한 번당 O(Q + M + N) 이 걸릴것이다.

N은 각 그룹에 속한 원소들을 모두 더하면 전체 노드가 되므로 있으며

Q는 간선을 하나씩 이어가야하므로 있고, M은 그룹이 M개라 있다. 패러럴 바이너리 서치를 모르면

설명하기가 좀 애매하다ㅠ 아무튼 각 그룹마다 lo, hi 가 있을 텐데 어찌됐던 모든 그룹들은

hi - lo , 즉 간격이 반씩 줄어드므로 반복문은 lgQ 번 돌게된다.

그러므로 최종적으로 시간 복잡도는 O((Q + M + N)lgQ) 이다.

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int lo[100003], hi[100003];
vector<int> query[100003];
int grp[100003];
int cnt[100003];
int N, M, Q;
vector<int> G[100003];
pair<int,int> edges[100003];
vector<int> mem[100003];
int vis[100003];
int par[100003];
int find(int u){
    return u == par[u] ? u : par[u] = find(par[u]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if(a == b) return;
    par[a] = b;
}
int main() {
    fastio();
    cin >> N >> M >> Q;
    for(int i = 0 ; i < N; i++) {
        cin >> grp[i];
        grp[i]--;
        cnt[grp[i]]++;
        mem[grp[i]].pb(i);
    }
    for(int i = 0 ; i < Q; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        edges[i] = {a, b};
    }
    for(int i = 0 ; i < M; i++) lo[i] = 0, hi[i] = Q;
    while(1){
        int isEnd = 1;
        for(int i = 0 ; i < M; i++){
            if(lo[i] < hi[i]){
                int mid = (lo[i] + hi[i]) / 2;
                query[mid].pb(i);
                isEnd = 0;
            }
        }
        if(isEnd) break;
        for(int i = 0 ; i < N; i++) par[i] = i;
        for(int i = 0 ; i < Q; i++){
            auto e = edges[i];
            merge(e.first, e.second);
            while(sz(query[i])){
                int id = query[i].back();
                query[i].pop_back();
                int grpId = find(mem[id][0]);
                int ok = 1;
                for(int nd : mem[id]){
                    if(find(nd) != grpId) {
                        ok = 0;
                        break;
                    }
                }
                if(!ok) lo[id] = i + 1;
                else hi[id] = i;
            }
        }
    }
    for(int i = 0 ; i < M; i++) {
        int ans = 0;
        if(cnt[i] == 1) ans = 0;
        else if(lo[i] == Q) ans = -1;
        else ans = lo[i] + 1;
        cout << ans << '\n';
    }
    return 0;
}