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;
}
}