[kuangbin带你飞]专题五并查集-526互联

Wireless Network POJ - 2236

题意：n台电脑，坐标(x,y)，电脑通讯范围为d；一开始，给出所有电脑坐标，然后所有电脑初始状态都是坏的，题目输入两个操作，第一修电脑且这台电脑可对d范围内正常电脑进行通讯了；第二就是查询，两台电脑是否可以通讯？

算法：并查集

思路：第一次，我直接通过坐标判断，那些电脑之间存在可通讯路径，存储起来，然后每次修电脑就激活合并并查集，然后查询的时候，再查两台电脑的父亲是否一样？然后TLE了。后面我把路径判断放在了修电脑操作里面了，就AC了

难点：这里要注意就是，修了的电脑才能正常通讯，坏电脑根本不运作；然后就是上面提到的TLE问题。

查看代码


#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;

int fa[1010];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unity(int x,int y){fa[find(y)] = find(x);}

int n,e;
int pX[1010],pY[1010];
bool ck[1010];
bool check(int a,int b,int c,int d){return (c-a)*(c-a)+(d-b)*(d-b) <= e*e;}

int main(){
    cin>>n>>e;
    for(int i=1;i<=n;i++) fa[i]=i,cin>>pX[i]>>pY[i];
    char ch;
    while(cin>>ch){
        int a,b;
        if(ch=='O'){
            cin>>a;ck[a] = true;
            for(int i=1;i<=n;i++) if(ck[i]&&check(pX[a],pY[a],pX[i],pY[i])) unity(a,i);
        }else{
            cin>>a>>b;
            if(find(a)==find(b)) puts("SUCCESS");
            else puts("FAIL");
        }
    }
}

The Suspects POJ - 1611

题意：多个测试用例，n个学生，m个小组，每个小组里面的人只要有一人，是潜在病毒携带者，其他人都要遭殃；学生0已经确定是了。然后问你有多少个学生是可能的病毒携带者。

算法：并查集

思路：每个组的学生都进行并查集合并，将他们父亲变成同一个祖先，最后查一下，有那些学生是和学生0同一个祖先就行了

查看代码

 #include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;

int fa[30010];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unity(int x,int y){fa[find(y)] = find(x);}

int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        for(int i=0;i<n;i++) fa[i] = i;
        while(m--){
            int _;cin>>_;
            int a;cin>>a;_--;
            while(_>0&&_--){
                int b;cin>>b;
                unity(a,b);
            }
        }
        int a = find(0),ans=0;
        for(int i=0;i<n;i++) if(find(i)==a) ans++;
        cout<<ans<<endl;
    }
}

How Many TablesHDU - 1213

题意：给你n个人，m个关系，然后有关系的人可以安排在同一桌，问最少需要多少桌开饭？

算法：并查集

思路：和上题大差不差，并查集，合并然后查询就行了。

查看代码

 #include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;

int fa[1010];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unity(int x,int y){fa[find(y)] = find(x);}

int main(){
    int _;cin>>_;
    while(_--){
        int n,m;cin>>n>>m;
        for(int i=1;i<=n;i++) fa[i] = i;
        while(m--){
            int a,b;cin>>a>>b;
            unity(a,b);
        }
        int ans = 0;
        for(int i=1;i<=n;i++) if(fa[i] == i) ans++;
        cout<<ans<<endl;
    }
}

How Many Answers Are WrongHDU - 3038

题意：a玩家自己写一串数字串，然后b玩家开始问连续子串的和，a玩家在逻辑冲突前的回答都正确——即当出现两个答案不同的时候，第一个出现的是正确答案。

算法：带权并查集

思路：看这题区间和，就想到区间数组，但是一看不对阿，这题是并查集，然后百度一下，是新东西（带权并查集），通过大牛博客学习：https://blog.csdn.net/hzf0701/article/details/109003395；接下来是我的理解，你把数组value，理解成向量，然后再看代码就豁然开朗；

难点：第一就是带权并查集的理解；第二就是区间（这里不是很懂，借鉴别人博客https://www.cnblogs.com/fighlone/p/13526864.html），必须左开右闭或者左闭右开

查看代码

 #include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 200000 + 10;

int fa[MAXN];
int value[MAXN];
int ans;
int find(int x){
    if(x==fa[x]) return x;
    else{
        int temp = fa[x];
        fa[x] = find(fa[x]);
        value[x] += value[temp];
        return fa[x];
    }
}
void unity(int x,int y,int v){
    int faX = find(x),faY = find(y);
    if(faX != faY){
        fa[faX] = faY;
        value[faX] = -value[x]+value[y]+v;
    }else{
        if(value[x]-value[y]!=v) ans++;
    }
}

int main(){
    int n,m;
    while(cin>>n>>m){
        ans = 0;
        for(int i=1;i<=n+1;i++) fa[i] = i , value[i] = 0;
        while(m--){
            int a,b,c;cin>>a>>b>>c;
            b++;
            unity(a,b,c);
        }
        cout<<ans<<endl;
    }
}