食物链
动物王国中有三类动物 A,B,CA,B,C，这三类动物的食物链构成了有趣的环形。
AA 吃 BB，BB 吃 CC，CC 吃 AA。
现有 NN 个动物，以 1∼N1∼N 编号。
每个动物都是 A,B,CA,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 NN 个动物所构成的食物链关系进行描述：
第一种说法是 1 X Y，表示 XX 和 YY 是同类。
第二种说法是 2 X Y，表示 XX 吃 YY。
此人对 NN 个动物，用上述两种说法，一句接一句地说出 KK 句话，这 KK 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 XX 或 YY 比 NN 大，就是假话；
- 当前的话表示 XX 吃 XX，就是假话。
你的任务是根据给定的 NN 和 KK 句话，输出假话的总数。
输入格式
第一行是两个整数 NN 和 KK，以一个空格分隔。
以下 KK 行每行是三个正整数 D，X，YD，X，Y，两数之间用一个空格隔开，其中 DD 表示说法的种类。
若 D=1D=1，则表示 XX 和 YY 是同类。
若 D=2D=2，则表示 XX 吃 YY。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤500001≤N≤50000,
0≤K≤1000000≤K≤100000
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例：
3首先， 在带扩展域的并查集 中 x 不再只是一个 值，而是一个事件；
规定 x 为 "事件 x 为 A 类动物"；
规定 x + N 为 "事件 x 为 B 类动物"；
规定 x + N * 2 为 "事件 x 为 C 类动物"；
p[find(X)] = find(Y) 表示
事件 X 为 A 类动物 和 事件 Y 为 A 类动物 同时发生
X 与 Y 为同种动物 等价于
p[ find(X) ] = find(Y);
p[ find(X + N)] = find(Y + N);
p[ find(X + N * 2)] = find(Y + N * 2);
p[find(X)] = find(Y + N) 表示
事件 X 为 A 类动物 和 事件 Y 为 B 类动物 同时发生
X 吃 Y 等价于
p[ find(X) ] = find(Y + N);
p[ find(X + N)] = find(Y + N * 2);
p[ find(X + N * 2)] = find(Y);
#include <bits/stdc++.h>
using namespace std;
const int N = 50000 + 10;
int p[N], d[N];
int find(int x)
{
if(p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
}
int main()
{
int res = 0;
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) p[i] = i;
while(m--)
{
int t, x, y;
cin >> t >> x >> y;
if(x > n || y > n) res++;
else
{
int px = find(x), py = find(y);
if(t == 1)
{
if(px == py && (d[x] - d[y] ) % 3) res++;
else if(px != py)
{
p[px] = p[py];
d[px] = d[y] - d[x];
}
}
else
{
if(px == py && (d[x] -d[y] - 1) % 3) res ++ ;
else if(px != py)
{
p[px] = p[py];
d[px] = d[y] - d[x] + 1;
}
}
}
}
cout << res;
}现有一块大奶酪，它的高度为 hh，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。
我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z=0z=0，奶酪的上表面为 z=hz=h。
现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。
如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去?
空间内两点 P1(x1,y1,z1)、P2(x2,y2,z2)P1(x1,y1,z1)、P2(x2,y2,z2) 的距离公式如下：
dist(P1,P2)=(x1−x2)2+(y1−y2)2+(z1−z2)2−−−−−−−−−−−−−−−−−−−−−−−−−−−−√dist(P1,P2)=(x1−x2)2+(y1−y2)2+(z1−z2)2
输入格式
每个输入文件包含多组数据。
输入文件的第一行，包含一个正整数 TT，代表该输入文件中所含的数据组数。
接下来是 TT 组数据，每组数据的格式如下：
第一行包含三个正整数 n，hn，h 和 rr，两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。
接下来的 nn 行，每行包含三个整数 x、y、zx、y、z，两个数之间以一个空格分开，表示空洞球心坐标为 (x,y,z)(x,y,z)。
输出格式
输出文件包含 TT 行，分别对应 TT 组数据的答案，如果在第 ii 组数据中，Jerry 能从下表面跑到上表面，则输出 Yes，如果不能，则输出 No。
数据范围
1≤n≤10001≤n≤1000,
1≤h,r≤1091≤h,r≤109,
T≤20T≤20,
坐标的绝对值不超过109109
输入样例：
3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4
输出样例：
Yes
No
YesThis 题，其实是一道并查集，刚看到的时候以为是……暴力枚举。
没想到吧！
这道题呢，就是求在三维空间内有没有一条从底面到最顶端的一条通道，然而每个点都是一个球形。
两个点相连通的前提，是两个点的球面相切或两个球相交。
既然如此，我们就可以写出如果两个点连通，那么他们必定满足什么条件：dist(x1, x2, y1, y2, z1, z2) <= r * 2。
其中dist表示点x1,y1,z1和点x2,y2,z2之间的距离，题目中有给出计算公式是（太难写了，看题去吧）……………………
如果两个点相连通，那么就可以表示为他们在同一个集合内，很好理解吧。
所以，如果有一个与底面相切或相交的球和一个与最顶端相切或相交的球在同一个集合内，就说明这两个球连通，在同一个集合内，那就说明有一条路径从底面到达最顶端，输出Yes，否则输出No。
所以，我们只需要遍历一遍所有的球，相互匹配，求出集合即可，接着就是双重循环判断是否有一对球，一个在顶端，一个在底端，是在一个集合内的。
那么代码就很好写了：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010;
int p[N];
int t;
int n, h, r;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct node
{
int x, y, z;
}nodes[N];
signed main()
{
cin >> t;
while(t--)
{
cin >> n >> h >> r;
for(int i = 0; i <= n+ 1; i++) p[i] = i;
for(int i = 1; i <= n; i++)
{
int x, y, z;
cin >> x >> y >> z;
nodes[i] = {x, y, z};
if(abs(z) <= r) p[find(i)] = find(0);
if(abs(z - h) <= r) p[find(i)] = find(n + 1);
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
int dx = nodes[i].x - nodes[j].x;
int dy = nodes[i].y - nodes[j].y;
int dz = nodes[i].z - nodes[j].z ;
if(dx * dx + dy * dy + dz * dz <= 4 * r * r)
p[find(i)] = find(j);
}
}
if(find(0) == find(n + 1)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}但是还有更好的算法吗？
并查集虽然能过，但效率并不高。
借助着并查集的思维，我们还可以扩展出BFS。
从底部的每一个球，向上搜索，直到到达一个顶部的球或队列为空（所有球都遍历过）为止输出答案。
每个球有且仅被遍历一次，但是每个遍历到的球都要访问一遍其他的球以确认是否在一个集合内（可以到达），所以时间复杂度也是O(n2)