# 神说光不够亮，带权并查集就有了

xiaoxiao2021-03-01  10

并查集学的不扎实的参考： 神说要有光

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：数量权

#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; }

//神说系列的神都是指我不知道名字的神牛！