关于并查集的介绍可以看我之前的文章并查集 Union Find
POJ 2236
很水的并查集题目，结构体中除了存坐标x,y以外还要存是否被维修过
合并的时候考虑的点比较多，假如当前修好的计算机编号是p，合并需要同时满足三个条件：1.合并的计算机编号不是p；2.合并的计算机与p的距离小于等于d；3.合并的计算机也是好的
import java.util.*;
public class Main {
public static class Node {
int x, y;
boolean isGood;
Node(int x, int y, boolean isGood) {
this.x = x;
this.y = y;
this.isGood = isGood;
}
}
public static class unionFindSet {
public HashMap<Node, Node> fatherMap;
public HashMap<Node, Integer> sizeMap;
public unionFindSet() {
fatherMap = new HashMap<Node, Node>();
sizeMap = new HashMap<Node, Integer>();
}
public void makeSets(List<Node> nodes) {
fatherMap.clear();
sizeMap.clear();
for (Node node : nodes) {
fatherMap.put(node, node);
sizeMap.put(node, 1);
}
}
private Node findHead(Node node) {
Node father = fatherMap.get(node);
if (father != node)
father = findHead(father);
fatherMap.put(node, father);
return father;
}
public boolean isSameSet(Node a, Node b) {
return findHead(a) == findHead(b);
}
public void union(Node a, Node b) {
if (a == null || b == null) {
return;
}
Node aHead = findHead(a);
Node bHead = findHead(b);
if (aHead != bHead) {
int aSetSize = sizeMap.get(aHead);
int bSetSize = sizeMap.get(bHead);
if (aSetSize <= bSetSize) {
fatherMap.put(aHead, bHead);
sizeMap.put(bHead, aSetSize + bSetSize);
} else {
fatherMap.put(bHead, aHead);
sizeMap.put(aHead, aSetSize + bSetSize);
}
}
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int d = cin.nextInt();
unionFindSet ufd = new unionFindSet();
List<Node> list = new LinkedList<Node>();
for (int i = 0; i < n; i++) {
int x = cin.nextInt();
int y = cin.nextInt();
list.add(new Node(x, y, false));
}
ufd.makeSets(list);
while (cin.hasNext()) {
String start = cin.next();
if (start.equals("O")) {
int p = cin.nextInt();
Node a = list.get(p - 1);
a.isGood = true;
list.set(p - 1, a);
for (int i = 0; i < list.size(); i++)
if (i != p - 1 && list.get(i).isGood && distance(a, list.get(i)) <= d * d)
ufd.union(a, list.get(i));
} else if (start.equals("S")) {
int p = cin.nextInt();
int q = cin.nextInt();
if (ufd.isSameSet(list.get(p - 1), list.get(q - 1)))
System.out.println("SUCCESS");
else
System.out.println("FAIL");
}
}
}
static double distance(Node a, Node b) {
return Math.pow((a.x - b.x), 2) + Math.pow((a.y - b.y), 2);
}
}POJ 1182
经典的种类并查集问题，我在这道题上卡了至少有一个星期才搞懂
比较简单的并查集开一倍空间存节点即可，但是这道题需要开三倍空间，我们把这三个空间分别记为A、B、C，对于任意一只动物，三个空间中都存有，比方说总共有N只动物，第i只动物的编号是i，那么在A、B、C三个空间中的编号分别为i、i + N、i + (N << 1)
这三个空间A、B、C之间相互有一定的关系，A中的所有动物吃B中的所有动物；B中的所有动物吃C中的所有动物；C中的所有动物吃A中的所有动物
在不考虑矛盾的情况下，合并同种动物a和b的代码如下
conn(a, b)
conn(a + N, b + N)
conn(a + (n << 1), b + (n << 1))上面代码很好理解，就是将A空间内的a和b，以及B空间内的a和b；C空间内的a和b合并
由于三个空间具有相互捕食的关系，因此如果有动物a吃动物b，他们之间的合并代码应该如下所示
conn(a, b + N)
conn(a + N, b + (n << 1))
conn(a + (N << 1), b)如果这里不理解，就回过头仔细看看A、B、C三个空间的关系
上面是不考虑矛盾的情况，实际上在所有的合并之前，应该考虑会不会存在矛盾，下面我们探讨如何判断矛盾
假设动物a和b是同一物种，那就去查询a和b + N、a和b + (N << 1)是否在同一个集合内，前者判断的是a是否吃b，后者判断的是b是否吃a，只要这两者满足其一，就和当前的操作矛盾（当前操作是a与b是同一物种）
假设a吃b，那就去查询a和b、a和b + (N << 1)是否在同一集合内，前者判断a和b是否是同一物种，后者判断b是否吃a（不可能存在a吃b，b也吃a），只要这两者满足其一，就和当前的操作矛盾（当前操作是a吃b）
#include <iostream>
using namespace std;
int n, m;
int f[150004];
int size[150004];
int find(int a) {
if (f[a] == a)
return a;
return f[a] = find(f[a]);
}
bool same(int a, int b) {
return find(a) == find(b);
}
void conn(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) {
int sa = size[fa];
int sb = size[fb];
if (sa <= sb) {
f[fa] = fb;
size[fb] = sa + sb;
} else {
f[fb] = fa;
size[fa] = sa + sb;
}
}
}
int main() {
int ans = 0;
scanf("%d %d", &n, &m);
for (int i = 0; i <= (n << 1) + n; i++) {
f[i] = i;
size[i] = 1;
}
for (int i = 0; i < m; i++) {
int op, a, b;
scanf("%d %d %d", &op, &a, &b);
if (a > n || b > n || a < 1 || b < 1)
ans++;
else if (op == 2 && a == b)
ans++;
else if (op == 1) {
if (same(a, b + n) || same(a, b + (n << 1)))
ans++;
else {
conn(a, b);
conn(a + n, b + n);
conn(a + (n << 1), b + (n << 1));
}
} else {
if (same(a, b) || same(a, b + (n << 1)))
ans++;
else {
conn(a, b + n);
conn(a + n, b + (n << 1));
conn(a + (n << 1), b);
}
}
}
printf("%d\n",ans);
} POJ 1703
题目大意是说，有两类团伙，输入D a b表示确认a和b是不同的团伙，输入A a b表示查询a和b是否是同一团伙
和食物链相比这算是比较简单的种类并查集，问题在于如何处理不同的关系，并查集维护的是相同的集合，但这道题维护的是不同的
具体做法是开两倍空间A和B，第i个人在A和B空间的编号分别为i,i + N。conn(a, b)表示a和b属于同一集合，conn(a, b + n)和conn(a + n, b)表示a和b属于不同集合
如果a和b是同伙，则same(a, b)或same(a + n, b + n)返回true
如果a和b不是同伙，则same(a, b + n)或same(a + n, b)返回true
如果上面两种情况都没有，说明这两个人暂时不知道什么关系
#include <iostream>
using namespace std;
int n, m;
int f[200005];
int find(int a) {
if (f[a] == a)
return a;
return f[a] = find(f[a]);
}
bool same(int a, int b) {
return find(a) == find(b);
}
void conn(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb)
f[fa] = fb;
}
int main() {
int ans = 0;
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 0; i <= (n << 1); i++)
f[i] = i;
for (int i = 0; i < m; i++) {
char op;
int a, b;
scanf("\n%c%d%d", &op, &a, &b);
if (op == 'D') {
conn(a, b + n);
conn(a + n, b);
} else {
if (same(a, b + n) || same(a + n, b))
printf("In different gangs.\n");
else if (same(a, b) || same(a + n, b + n))
printf("In the same gang.\n");
else
printf("Not sure yet.\n");
}
}
}
return 0;
}AOJ 2170
这题目我看了半天实在是看不太懂，最后找谷歌翻译了全篇
大意是说输入N个点，Q次操作。接下来输入N-1行数据，第一行输入p1表示第2个点的父节点是p1，第二行输入p2表示第3个点的父节点是p2。然后输入Q-1行操作，M a表示标记a点，Q b表示询问离b最近的被标记的祖先
水题，标记这个操作其实可以看作将节点的父节点指向自己，即将当前节点从其父节点中分离出来，但是跟在当前节点后面的所有节点还是跟着自己
为了保证节点间的关系，不能使用路径压缩
#include <stdio.h>
#define ll long long
int f[100001];
int find(int a) {
return a == f[a] ? a : find(f[a]);
}
int main() {
ll n, m;
while (scanf("%lld %lld", &n, &m) != EOF && n + m) {
for (int i = 2; i <= n; i++)
scanf("%d", &f[i]);
f[1] = 1;
ll ans = 0;
char op[5];
int t;
for (int i = 0; i < m; i++) {
scanf("%s%d",op, &t);
if (op[0] == 'Q')
ans += find(t);
else
f[t] = t;
}
printf("%lld\n", ans);
}
return 0;
} 