Travel 并查集

题意：给一个图，若干询问，每次询问只经过边权<=w的边，x能到达的点数

并查集啊，对询问和边排序，直接合并，维护size，查询

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 105000
using namespace std;
int fa[N],size[N],n,m,k;
struct data{
    int u,v,w;
}d[4*N];
bool cmpd(data a,data b){return a.w<b.w;}
struct query{
    int u,w,ans,id;
}q[N];
bool cmpq(query a,query b){return a.w<b.w;}
bool back(query a,query b){return a.id<b.id;}
int find(int x){
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
void hb(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    fa[y]=x;size[x]+=size[y];
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){fa[i]=i;size[i]=1;}
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&d[i].u,&d[i].v,&d[i].w);
    sort(d+1,d+m+1,cmpd);
    for(int i=1;i<=k;i++){
        scanf("%d%d",&q[i].u,&q[i].w);
        q[i].id=i;
    }
    sort(q+1,q+k+1,cmpq); q[k+1].w=q[k].w+1;
    int now=q[1].w,ee=1,pos=1;
    while(now<=q[k].w){
        for(;ee<=m&&d[ee].w<=now;ee++)
            hb(d[ee].u,d[ee].v);
        for(;q[pos].w==now;pos++)
            q[pos].ans=size[find(q[pos].u)];
        now=q[pos].w;
    }
    sort(q+1,q+k+1,back);
    for(int i=1;i<=k;i++)
        printf("%d
",q[i].ans);
    return 0;
}