FUCKING CRAZY! 食物链太难了
并查集
快速地处理
- 将两个集合合并
- 询问两个元素是否在一个集合当中
比如 belong[x] 存储的是 x 属于哪一个集合，比如 belong[x] = a 代表 元素 x 属于 集合 a
那么我们就可以用 O(1) 来判断 元素 x 和 y 是否在同一个集合中
if(belong[x] == belong[y])
但是如果要合并一个 1000个元素的集合 和 2000个元素的集合，那么我们至少要做 1000 次操作
但是并查集可以在近乎 O(1) 的时间内完成这两个操作
基本原理
用树的形式来维护每一个集合
每一个集合的根节点元素 (root) 就是她的代表元素，根节点的编号就是我当前集合的编号
对于每一个点，我们都存储她的父节点是谁，p[x] 表示他的父节点是谁，p[p4] = p1
当我们要求某一个点属于哪一个集合的时候，比方说 找 p4 属于哪一个集合，我们可以根据他的 father 依次往上找，直到根节点为止
//问题1 如何判断树根
if(p[x] == x)
//问题2 如何求 x 的集合编号
while(p[x]!=x)
{
x = p[x];
}
//问题3 如何合并两个集合，加一条边：px 是 x 的集合编号，py 是 y 的集合编号
p[x] = y;
压缩路径优化
当我们查询一个元素 pp4 在哪个集合中的时候，我们将他这个路径上的所有点，全部存到根节点下
模板
(1)朴素并查集：
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
(2)维护size的并查集：
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
练习
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为
M a b或Q a b中的一种。输出格式
对于每个询问指令
Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出Yes，否则输出No。每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4输出样例：
Yes No Yes
#include<iostream>
using namespace std;
const int N = 100010;
int n,m;
int p[N];
int find(int x) //返回 x 的祖宗结点
{
if(p[x]!=x)
{
p[x] = find(p[x]);
}
return p[x];
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1;i <= n ;i++)
{
p[i] = i;
}
while(m--)
{
char op;
int a,b;
cin >> op >> a >> b;
if(op == 'M')
{
p[find(a)] = find(b);
}else if(op == 'Q'){
if(find(a) == find(b))
{
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
}
return 0;
}
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；Q2 a，询问点 a 所在连通块中点的数量；输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为
C a b，Q1 a b或Q2 a中的一种。输出格式
对于每个询问指令
Q1 a b，如果 aa 和 bb 在同一个连通块中，则输出Yes，否则输出No。对于每个询问指令
Q2 a，输出一个整数表示点 a 所在连通块中点的数量每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5输出样例：
Yes 2 3
连通块：如果 从 点 a 可以走到 b，从 b 也可以走到 a，那么说明 a 和 b 属于同一连通块
我们可以用集合来维护连通块，当我们在两个连通块之间连一条边的时候，其实就是将两个集合进行合并
#include<iostream>
using namespace std;
const int N = 100010;
int n,m;
int p[N];
int Size[N];
int find(int x) //返回 x 的祖宗结点
{
if(p[x]!=x)
{
p[x] = find(p[x]);
}
return p[x];
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1;i <= n ;i++)
{
p[i] = i;
Size[i] = 1;
}
while(m--)
{
char op[5];
int a,b;
cin >> op;
if(op[0] == 'C')
{
cin >> a >> b;
if(find(a) == find(b))
{
continue;
}
Size[find(b)] += Size[find(a)];
p[find(a)] = find(b);
}else if(op[1] == '1'){
cin >> a >> b;
if(find(a) == find(b))
{
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}else{
cin >> a;
cout << Size[find(a)] << endl;
}
}
return 0;
}
动物王国中有三类动物 A,B,C这三类动物的食物链构成了有趣的环形。
A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1∼N 编号。
每个动物都是 A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是
1 X Y，表示 X 和 Y 是同类。第二种说法是
2 X Y，表示 X 吃 Y。此人对 NN 个动物，用上述两种说法，一句接一句地说出 KK 句话，这 KK 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 X 或 Y 比 N 大，就是假话；
- 当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式
第一行是两个整数 N 和 K，以一个空格分隔。
以下 K 行每行是三个正整数 D，X，Y两数之间用一个空格隔开，其中 D 表示说法的种类。
若 D=1，则表示 X 和 Y 是同类。
若 D=2，则表示 X 吃 Y。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤50000
0≤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
我们通过维护并查集的 子节点到 root 结点的距离来实现 食物链
比如 1 到 root 结点的距离是 1，说明 1 被 root 吃，4 到 root 的距离是 1，说明 4 被 root 吃
2 到 root 的距离是 2，说明 2 被 到 root 距离为 1 的结点吃
3 到 root 的距离是 3，说明 3 被 到 root 距离为 2 的结点吃，同时可以吃到 root 距离为 1的结点
#include <iostream>
using namespace std;
const int N = 50010;
int n, m;
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;
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int res = 0;
while (m -- )
{
int t, x, y;
scanf("%d%d%d", &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] = py;
d[px] = d[y] - d[x];
}
}
else
{
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d\n", res);
return 0;
}
原文地址：http://www.cnblogs.com/ShibuyaKanon/p/16794973.html
