并查集是一个树形的数据结构， 可以用来处理集合的问题， 也可以用来维护动态连通性，或者元素之间关系的传递（关系必须具有传递性才能有并查集来维护，因为并查集有压缩路径）。
用并查集来维护元素之间关系的传递， 那么元素与元素之间就有一个权值（带权并查集），那么当路径压缩时，我们需要根据关系的传递性来维护
当父元素变动时，关系的变动。
给定一些元素之间的关系， 问我们有多少是错误的。 当碰到一个错误时，并不会用它来更新并查集（错误的怎么用来更新？），只会把ans++
我们用0表示与父亲是同类， 用1表示吃父亲 ， 用2表示被父亲吃。（这表示的是我与父亲的关系,即箭头是由我指向父亲）， 那怎么得到父亲与我的关系呢？
只要将箭头的方向改变， 就得到了父亲与我的关系， (3-rank[x]) % 3 就是了
只要明白了箭头方向的改变，关系也可以用公式推导出来
那么下边就好办了， 如果判断是否发生错误呢？
如图，红色的线表示题目给我们的关系， 现在他们在一个集合里面，可以通过运算获得蓝线1，然后再通过计算获得蓝线2， 只要将蓝线2和红线对比，就知道
题目所给的关系是否正确。
同理，集合的合并也是一样的
通过红线1，依次算出蓝线1，2，3. 那么就可以进行集合的合并了。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/*
路径压缩的时候要保留结点与结点之间的关系， 所以要维护的一个信息是，结点之间的关系
0同类 ， 1被父亲吃， 2吃父亲
*/
const int N = + ;
int fa[N];
int id[N];//id[u] 表示与父亲之间的边的权值，， 权值为0，1，2三种
int find(int x)
{
if (x == fa[x])
return x;
//路径压缩的时候，由于父亲的改变， 需要改变权值
int tmp = fa[x];
fa[x] = find(fa[x]);
id[x] = (id[x] + id[tmp]) % ;
return fa[x];
}
int main()
{
int n, m, ans;
int d, a, b;
int fx, fy;
//while (scanf("%d%d", &n, &m) != EOF)
{
scanf("%d%d", &n, &m);
ans = ;
for (int i = ; i <= n; ++i)
{
fa[i] = i;
id[i] = ;
}
while (m--)
{
scanf("%d%d%d", &d, &a, &b);
if (d == )
{
if (a > n || b > n)
ans++;
else
{
fx = find(a);
fy = find(b);
if (fx != fy)
{
fa[fy] = fx;
id[fy] = (( - id[b])% + (d - ) + id[a]) % ;
}
else
{
if ((-id[a]+id[b])% != )
ans++; }
}
}
else
{
if (a > n || b > n)
ans++;
else
if (a == b)
ans++;
else
{
fx = find(a);
fy = find(b);
if (fx != fy)
{
fa[fy] = fx;
id[fy] = (( - id[b])% + (d - ) + id[a]) % ;
}
else
{
if (( - id[a] + id[b])% != )
ans++;
}
}
}
}
printf("%d\n", ans);
}
return ;
}
有连续的一段数，数字是什么谁都不知道， 但是呢有限制条件。
ai bi c 表示 下标ai到bi的这一段数的和为c
现在给我们m个限制条件，问我们有多少个限制条件与前面的条件矛盾
分析：依旧考察关系的传递， 只不过关系需要转换。 即 sum[bi] - sum[ai-1] = c
然后ai-1作为父亲， bi作为儿子， 权值为两者的差值。
其余的都和食物链那题差不多了。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/*
给定一些约束条件， 问有多少个错误的
*/
const int N = + ;
int fa[N], r[N];
int find(int x)
{
if (x == fa[x])return x;
int f = fa[x];
fa[x] = find(fa[x]);
r[x] = r[x] + r[f];
return fa[x];
}
int main()
{
int n, m;
int a, b, fx, fy,w;
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = ; i <= n; ++i)
{
fa[i] = i;
r[i] = ;
}
int ans = ;
while (m--)
{
scanf("%d%d%d", &a, &b,&w);
a--;
fx = find(a);
fy = find(b);
if (fx != fy)
{
fa[fy] = fx;
r[fy] = w + r[a] - r[b];
}
else if (r[b] - r[a] != w)
ans++;
}
printf("%d\n", ans);
}
return ;
}
有长度为n的01序列， 有m个限制条件
ai bi even/odd 表示从ai到bi， 1的个数为偶数/奇数
限制条件有可能相互矛盾， 题目要我们求出从哪里开始出现矛盾
和上面那题一条的， cnt[bi] - cnt[ai-1] 表示从ai到bi的1的个数
然后ai-1作为父亲， bi作为儿子， 如果两者相减是偶数， 那么权值为0，如果是奇数， 权值为1.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = << ;
/* */
std::map<int, int> ma;
const int N = + ;
int fa[N], rank[N];
int find(int x)
{
if (x == fa[x])
return x;
int f = fa[x];
fa[x] = find(fa[x]);
rank[x] = (rank[x] + rank[f]) % ;
return fa[x];
}
int main()
{
int n, m;
int a, b, fx, fy, d;
char str[];
scanf("%d%d", &n, &m);
for (int i = ; i < N; ++i)
{
fa[i] = i;
rank[i] = ;
}
int cnt = ;
int i;
for (i = ; i < m; ++i)
{
scanf("%d%d%s", &a, &b, str);
a--;
if (ma[a] == )
ma[a] = ++cnt;
a = ma[a];
if (ma[b] == )
ma[b] = ++cnt;
b = ma[b];
if (str[] == 'o')
d = ;
else
d = ;
fx = find(a);
fy = find(b);
if (fx != fy)
{
fa[fx] = fy;
rank[fx] = (rank[a] + rank[b] + d) % ;
}
else if ((rank[a] + rank[b]) % != d)
break;
}
printf("%d\n", i);
return ;
}
n个点， m行条件， 每行 F1 F2 L E/W/N/S 表示F2在F1的E/W/N/S方向， 且距离为L
然后有q个询问，每个询问F1 F2 i 表示在已知前i个条件的情况下，求F1和F2的笛卡尔距离。如果无法得到输出-1
分析：其实也是维护元素与元素之间的关系， 只不过关系是他们的笛卡尔距离， 同样的， 这种关系同样具有传递性
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/*
这次用并查集来维护的依旧是元素与元素之间的关系， 只不过关系是笛卡尔距离
*/
const int N = + ;
int fa[N], rx[N], ry[N];
int F1[N], F2[N], L[N], D[N];
int find(int x)
{
if (x == fa[x]) return x;
int f = fa[x];
fa[x] = find(fa[x]);
rx[x] = (rx[x] + rx[f]);
ry[x] = (ry[x] + ry[f]);
return fa[x];
} int main()
{
int n, m, q;
char str[];
int x, y, k, fx, fy;
int i;
while (scanf("%d%d", &n, &m) != EOF)
{
for ( i = ; i <= n; ++i)
{
fa[i] = i;
rx[i] = ry[i] = ;
}
for ( i = ; i <= m; ++i)
{
//E 用0表示
scanf("%d%d%d%s", &F1[i], &F2[i], &L[i], str);
if (str[] == 'W')
{
swap(F1[i], F2[i]);
D[i] = ;
}
else if (str[] == 'E')
D[i] = ;
else if (str[] == 'N')
{
swap(F1[i], F2[i]);
D[i] = ;
}
else
D[i] = ;
}
scanf("%d", &q);
i = ;
while (q--)
{
scanf("%d%d%d", &x, &y, &k);
for (; i <= k; ++i)
{
fx = find(F1[i]);
fy = find(F2[i]);
if (fx != fy)
{
fa[fy] = fx;
if (D[i] == )
{
//L[i] - rx[F2[i]] 得到fy与F1[i]的相对距离
//再加上F1[i]与fx的相对距离,得到了 fy与fx的相对距离
rx[fy] = rx[F1[i]] + L[i] - rx[F2[i]];
ry[fy] = ry[F1[i]] + - ry[F2[i]];
}
else
{
rx[fy] = rx[F1[i]] + - rx[F2[i]];
ry[fy] = ry[F1[i]] + L[i] - ry[F2[i]];
}
}
}
fx = find(x);
fy = find(y);
if (fx != fy)
puts("-1");
else
{
int ans = abs((rx[y] - rx[fy]) - (rx[x] - rx[fx])) + abs((ry[y] - ry[fy]) - (ry[x] - ry[fx]));
printf("%d\n", ans);
}
} }
return ;
}
逆向并查集，离线存储后，逆向过来建并查集
给定n个星球， 每个星球有能量值pi，
给定m条边， 表示
然后有两种操作 query a 找到与a连通的能力最大的星球（这个星球的能力要比a大），如果有多个最大的，那么输出编号最小的
destory a b 摧毁a和b之间的道路
并查集要删边很困难，但是我们可以逆向来建并查集。且维护一个集合的父亲为这个集合中权值最大的元素，如果权值相同则设编号小的为父亲
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
#include <unordered_map>
#include <unordered_map>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/*
给定n个星球， 每个星球有能量值pi，
给定m条边， 表示
然后有两种操作 query a 找到与a连通的能力最大的星球（这个星球的能力要比a大），如果有多个最大的，那么输出编号最小的 找到连通的？？？
set<pair<int,int> >; lower_bound(
*/
const int N = + ;
int val[N];
int fa[N];
int u[N * ], v[N * ];
int a[N * ], b[N * ], ans[N * ];
unordered_map<int, int> ma[N];//要开一个数组，
int find(int x)
{
if (fa[x] == x)
return x;
return fa[x] = find(fa[x]);
}
void unionSet(int x, int y)
{
int fx = find(x);
int fy = find(y);
if (fx != fy)
{
if (val[fx] > val[fy])
fa[fy] = fx;
else if (val[fx] < val[fy])
fa[fx] = fy;
else
{
if (fx < fy)
fa[fy] = fx;
else
fa[fx] = fy;
}
}
}
void input(int &x)
{
char ch = getchar();
while (ch<'' || ch>'')
ch = getchar();
x = ;
while (ch >= '' &&ch <= '')
{
x = x * + ch - '';
ch = getchar();
}
}
int main()
{
int n, q, m;
char query[];
int t = ;
while (scanf("%d", &n) != EOF)
{
if (t != )
puts("");
t++; for (int i = ; i < n; ++i)
{
ma[i].clear();
input(val[i]);
fa[i] = i;
}
input(m);
for (int i = ; i < m; ++i)
{
//scanf("%d%d", &u[i], &v[i]);
input(u[i]);
input(v[i]);
if (u[i] > v[i])
swap(u[i], v[i]);
}
input(q);
for (int i = ; i < q; ++i)
{
scanf("%s", query);
if (query[] == 'q')
{
a[i] = -;
input(b[i]);
}
else
{
input(a[i]);
input(b[i]);
if (a[i] > b[i])
swap(a[i], b[i]);
ma[a[i]][b[i]] = ;
}
}
for (int i = ; i < m; ++i)
{
if (ma[u[i]][v[i]]!=)
unionSet(u[i], v[i]);
}
for (int i = q - ; i >= ; --i)
{
if (a[i] == -)
{
int fx = find(b[i]);
if (val[fx] > val[b[i]])
ans[i] = fx;
else
ans[i] = -;
}
else
{
ans[i] = -;
unionSet(a[i], b[i]);
}
}
for (int i = ; i < q; ++i)
if (ans[i] != -)
printf("%d\n", ans[i]);
}
return ;
}