[c++] 백준 15586 MooTube (Gold)

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

15586번: MooTube (Gold)

유니온 파인드와 오프라인 쿼리 테크닉으로 해결할 수 있다.

"동영상 추천은 USADO가 K를 넘어야 가능하다"의 의미를 생각해 보면

 

간선이 제거된 상태에서, 간선의 비용이 큰 순으로 하나씩 추가하며

연결된 그룹의 정점들 수를 세면 된다는 것을 깨달을 수 있다.

쿼리를 내림차순 정렬하고, 쿼리의 k를 기준으로 간선을 조절하며 추가해 준다.

쿼리의 v가 있는 그룹의 정점의 수에 v 자기 자신을 뺀 것이 답이 된다.

(약간 최소 스패닝 트리 느낌이 난다.)

 

간선을 하나씩 추가하며 그룹을 관리하기 위해 유니온 파인드를 사용하고,

쿼리 순으로 답을 출력해야 하기 때문에 오프라인 쿼리를 사용한다.

(그룹의 수를 세어주기 위해 그룹의 수를 기록하는 배열도 만들어 주자.)

#include<bits/stdc++.h>
using namespace std;
#define N 100100
typedef long long ll;
int n,q;
int parent[N],group[N],ans[N];
vector<tuple<int,int,int>> graph,query;
int FIND(int x){
    if(parent[x] == x) return x;
    return parent[x] = FIND(parent[x]);
}
void MERGE(int a, int b){
    a=FIND(a), b=FIND(b);
    parent[a] = b;
    group[b] += group[a];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    for(int i=0; i<=n; i++)
        parent[i]=i, group[i]=1;
    for(int i=1; i<n; i++){
        int a,b,c; cin>>a>>b>>c;
        graph.push_back({c,a,b});
    }
    for(int i=0; i<q; i++){
        int k,v; cin>>k>>v;
        query.push_back({k,v,i});
    }
    sort(graph.rbegin(),graph.rend());
    sort(query.rbegin(),query.rend());
    int edge_idx=0;
    for(int t=0; t<q; t++){
        int k,v,idx;
        tie(k,v,idx) = query[t];
        while(edge_idx < n-1 && k<=get<0>(graph[edge_idx])){
            MERGE(get<1>(graph[edge_idx]),get<2>(graph[edge_idx]));
            edge_idx++;
        }
        ans[idx] = group[FIND(v)]-1;
    }
    for(int i=0; i<q; i++)
        cout << ans[i] << '\n';
    return 0;
}