并查集学的不扎实的参考： 神说要有光
带权并查集分两种：
1：种类权
我改的题面，不要喷谢谢
problem据中*大学某人发现了一个恐怖的事情，人类对同性恋的认可度越来越高。通过调查某校N对情侣（只记录了学号后几位保证不重复），得到了一组统计数据，可是，这你mb太多了，我需要你们看看这些人里面有没有同性恋InputThe first line of the input contains the number of tests. Each test starts with one line giving the number of person (between 1 and 2000) and the number of pairs(up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct person numbers separated by a single space. Persons are numbered consecutively starting from one.OutputThe output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the all the love is stable, or "Suspicious bugs found!" if there exist any love no stable. 每个输出后应有一空行。Sample Input 2 3 3 1 2 2 3 1 3 4 2 1 2 3 4Sample Output Scenario #1: Suspicious bugs found! Scenario #2: No suspicious bugs found! Hint Huge input,scanf is recommended.思路：
给不同类型的东西标不一样的号码。
难点：
合并时，无法保证两个集合中的数字与性别的映射关系相同。
解决方法：
代码内有注释，这里不兹论述
参考代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define scanf scanf_s#define s(x) scanf("%d",&x)#define M 50005int n, k, l, r;int pre[M];int gro[M];int find(int x) { if (x == pre[x])return x; int t = pre[x]; pre[x] = find(pre[x]); gro[x] = (gro[x] + gro[t]) % 2;//有两种性别，在向上比较过程中。如果A-B相连，A1,B0::A还是1，如果A1，B1，A变成0用余数改变状态 return pre[x];}bool unite(int a, int b) { int x = find(a); int y = find(b); if (x != y) { pre[y] = x; gro[y] = (3 + gro[a] - gro[b]) % 2;//在合并大集合的时候要保证让两个集合的根实现题意中的恋爱关系，即异性，如果A1,B1，会变成A0,B1再通过之后的find调配好所有的情况，是三不是一是为了保证不出现负数性别，影响判断 } else { if (gro[a] == gro[b])return true; } return false;}/*不要忘记初始化*/void init() { for (int i = 0; i <= n; i++)pre[i] = i, gro[i] = 0;}int main() { int t; s(t); for (int cas = 1; cas <= t; cas++) { bool f = false; s(n); s(k); init(); while (k--) { s(l); s(r); if (f)continue; f = unite(l, r); } printf("Scenario #%d:", cas); putchar('\n'); if (f) { printf("Suspicious bugs found!"); } else { printf("No suspicious bugs found!"); } putchar('\n'); putchar('\n'); }}
2：数量权
在简单并查集的基础上，抽象出集合的特征量，然后可以多开几个数组也可以搞个类（结构体）出来搞。难点在于数据的抽象。
把并查集特征值拿出来，这个东西可以参考这个题：
参考题
我校英语萌萌嗒的大佬翻译，看不懂可以去上面那个链接
给你N个点组成的一张无向图，要求对于任意的不同的三个点(x,y,z),如果存在(x,y),(y,z)就必须存在(x,z)。现问你它是否符合要求。Input第一行n,m（3 ≤ n ≤ 150 000,m ≤ 150 000 且合法） 接下来m行每行表示无向图的一条边Output合法输出YES，不合法输出NOSample1 Input 3 2 1 2 2 3 Output NO Sample2Input 4 3 1 3 3 4 1 4 Output YES Sample3Input 4 4 3 1 2 3 3 4 1 2 Output NO Sample4Input 10 4 4 3 5 10 8 9 1 2 Output YES我们把每个集合分出两种性质，一种是总边数，一种是总点数。
题目要我们保证同一连通体系（集合）中的元素两两联通，我们可以看到一个点有0的遍，再插入第二个点时，要与第一个点连接，在插入一个点到这个集合，就要和另外两个点连接，由此发现没增加一个点，增加n-1条边，根据等差数列性质得，2*l=（n*n-n)这个关系，剩下的就是储存。每次插入边不能给两个点都算一份，否则最后汇总时会发现两个点最后合并出两条边这种情况。
代码参考：：
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<set> using namespace std; #define s(x) scanf("%d",&x) #define p(x) printf("%d\n",x) #define s2(x,y) scanf("%d%d",&x,&y); typedef long long L; #include<vector> L n, m, x, y; L pre[150005]; L line[150005]; L node[150005]; L find(L x) { if (x == pre[x])return x; pre[x] = find(pre[x]); return pre[x]; } void unite(L x,L y) { L a=find(x); L b=find(y); if (a == b) { ++line[x]; } else { pre[a]= b; ++line[x]; } } void init() { for (L i = 0; i <= n; i++) { pre[i] = i; line[i] = 0; node[i] = 1; } } void add() { for (L i = 1; i <= n; i++) { find(i); if (pre[i] != i) { line[pre[i]] += line[i]; node[pre[i]] += node[i]; } } } #define scanf scanf_s int main() { s2(n, m); init(); while (m--) { s2(x, y); unite(x, y); } add(); for (L i = 1; i <= n; i++) { if (pre[i] == i) { if (node[i] * (node[i] - 1) != 2*line[i]) { printf("NO"); return 0; } } } printf("YES"); return 0; }并查集题组：：可以小组交流呦
想和宝宝聊聊可以加个关注，加个菜鸡交流群：639176311，老子是啥？答案：天下第一
//神说系列的神都是指我不知道名字的神牛！
