并查集 poj1988 Cube Stacking（并查集

使用并查集查找时，如果查找次数很多，那么使用朴素版的查找方式肯定要超时。比如，有一百万个元素，每次都从第一百万个开始找，这样一次运算就是10^6，如果程序要求查找个一千万次，这样下来就是10^13,肯定要出问题的。

　　这是朴素查找的代码,适合数据量不大的

int findx(int x)
{
int r=x;
while(parent[r] !=r)
r=parent[r];
return r;
}
 
 

下面是采用路径压缩的方法查找元素：

int find(int x) //查找x元素所在的集合,回溯时压缩路径
{
if (x != parent[x])
{
parent[x] = find(parent[x]); //回溯时的压缩路径
} //从x结点搜索到祖先结点所经过的结点都指向该祖先结点
return parent[x];
}

int findx(int x) {
if(x == pa[x]) return x;
int t = findx(pa[x]);
pa[x] = t;
return pa[x];
}
和上面那个一样。但最后一题这个比较好

for(int i = 1; i <= n; i++) {
        if(i == findx(i)) res++;
    }
//找有多少个连通分量。
 

上面是一采用递归的方式压缩路径，但是，递归压缩路径可能会造成溢出栈，我曾经因为这个RE了n次，下面我们说一下非递归方式进行的路径压缩：

接下来是合并的代码，保证能够把小的子树接到大的子树上面

有很多组学生，在同一个组的学生经常会接触，也会有新的同学的加入。但是SARS是很容易传染的，只要在改组有一位同学感染SARS，那么该组的所有同学都被认为得了SARS。现在的任务是计算出有多少位学生感染SARS了。假定编号为0的同学是得了SARS的。

解题思路---->显然并查集了。并查集的详细解释在可以点击并查集（不相交集合）进行学习。采用num[]存储该集合中元素个数，并在集合合并时更新num[]即可。然后找出0所在的集合的根节点x，因此，num[x]就是answer了。

Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#include <stdio.h>//by ktyanny  
#include <iostream>  
using namespace std;  
  
const int MAXN = 30001; /*结点数目上线*/  
int pa[MAXN];    /*p[x]表示x的父节点*/  
int rank[MAXN];    /*rank[x]是x的高度的一个上界*/  
int num[MAXN];/*num[]存储该集合中元素个数，并在集合合并时更新num[]即可*/  
  
void make_set(int x)  
{/*创建一个单元集*/  
    pa[x] = x;  
    rank[x] = 0;  
    num[x] = 1;  
}  
  
int find_set(int x)  
{/*带路径压缩的查找*/  
    /*保存待查找的数*/  
    int r = x, temp;  
    /*找到根节点*/  
    while(pa[r] != r) r = pa[r];  
    while(x != r)  
    {  
        temp = pa[x];  
        pa[x] = r;  
        x = temp;  
    }  
    return x;  
    //if(x != pa[x]) //注释掉的其实也是可以的，不过不想用递归来做啦  
    //    pa[x] = find_set(pa[x]);  
    //return pa[x];  
}  
  
/*按秩合并x，y所在的集合*/  
void union_set(int x, int y)  
{  
    x = find_set(x);  
    y = find_set(y);  
    if(x == y)return ;  
    if(rank[x] > rank[y])/*让rank比较高的作为父结点*/  
    {  
        pa[y] = x;  
        num[x] += num[y];  
    }  
    else   
    {  
        pa[x] = y;  
        if(rank[x] == rank[y])  
            rank[y]++;  
        num[y] += num[x];  
    }  
}  
  
//answer to 1611   
int main()  
{  
    int n, m, x, y, i, t, j;  
    while(scanf("%d%d", &n, &m))  
    {  
        if(m==n && n == 0) break;  
        if(m == 0)  
        {  
            cout << "1
"; continue;  
        }  
        for(i = 0; i < n; i++)  
            make_set(i);  （初始化）
        for(i = 0; i < m; i++)  
        {  
            scanf("%d", &t);  
            scanf("%d", &x);  
            for(j = 1; j < t; j++){  
                scanf("%d", &y);  
                union_set(x, y);  
                x = y;  
            }  
        }  
        x = find_set(0);/*找到0所在的树的树根*/  
        //int ans = 0;  
        //for(i = 0; i < n; i++)  
        //    if(pa[i] == x)  
        //        ans++;  
        //cout << ans << endl;  
        cout << num[x] << endl;  
    }  
    return 0;  
}  




下面的是自己写的

#include<cstdio>
#include<cstring>
using namespace std;

const int maxm = 3e4 + 5;
int pa[maxm], rank[maxm], num[maxm];

//去掉Num可以当板子用

void make_set(int x){
pa[x] = x;
rank[x] = 0;
num[x] = 1;
}

int findx(int x)  
{/*带路径压缩的查找*/  
    /*保存待查找的数*/  
    int r = x, temp;  
    /*找到根节点*/  
    while(pa[r] != r) r = pa[r];  
    while(x != r)  
    {  
        temp = pa[x];  
        pa[x] = r;  
        x = temp;  
    }  
    return x;  
    //if(x != pa[x]) //注释掉的其实也是可以的，不过不想用递归来做啦  
    //    pa[x] = find_set(pa[x]);  
    //return pa[x];  
}  //尽量还是不用递归写吧，可能会栈溢出

void unio(int x, int y) {
x = findx(x);
y = findx(y);
if(x == y)return ;
if(rank[x] > rank[y]) {
pa[y] = x;
num[x] += num[y];
}
else {
pa[x] = y;
if(rank[x] == rank[y]) {
rank[y]++;
}
num[y] += num[x];
}
}

int main() {
int n, m, x, y, i, t, j;
while(~scanf("%d%d", &n, &m)) {
if(m==n && n == 0) break;
for(i = 0; i < n; i++)
make_set(i);
for(i = 0; i < m; i++) {
scanf("%d", &t);
scanf("%d", &x);
for(j = 1; j < t; j++){
scanf("%d", &y);
unio(x, y);
}
}
x = findx(0);
printf("%d ", num[x]);
}
return 0;
}

https://blog.****.net/yoer77/article/details/62882150这是讲食物链的一篇。
escription

动物王国中有三类动物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。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

Input

第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

Output

只有一个整数，表示假话的数目。

Sample Input

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

Sample Output

3

题解:

并查集题型, 每种动物创建3个元素, i-A, i-B, i-C, 分别表示动物i属于A, 动物i属于B, 动物i属于C, 并用这3*N个元素来构造并查集.
并查集里面的每一个组表示组内的所有情况都同时发生或不发生.
对于每一条信息, 按照如下步骤操作:

T=1: 如果判断”x和y属于同一类”不会产生矛盾,则合并元素 x-A 和 y-A, x-B 和 y-B, x-C 和 y-C;
T=2: 如果判断”x吃y”不矛盾, 则合并元素 x-A 和 y-B , x-B 和 y-C, x-C 和 y-A;

其中判断x和y属于同一类是否会产生矛盾, 即判断”x-A, y-B为同一组, 或者 x-A, y-C同一组为同一组” 是否成立. 如果成立则说明之前已经确定过x,y动物之间的吃与被吃的关系,该句话与先前确定的状态产生了矛盾,这句话为假.
判断x吃y是否会产生矛盾, 即判断”x-A, y-A为同一组, 或者x-A, y-C为同一组”是否成立. 即判断x, y是否已经时同类, 或者已经时y吃x的关系. 如果是上述其中一种, 则该句话与之前已经产生的状态矛盾, 该句话为假.
判断x,y同类, 我们只需要判断x-A, y-A是否为同一组, 而不需要再判断x-B, y-B是否为同一组, 或者x-C, y-C是否为同一组, 因为这是冗余的判断,没有必要. 我们在合并元素的时候,已经把这样表示同样状态的3种状态都设置过了, 判断其中一种就可以了.

代码:
```
/*
 * runtime error 好多次,是因为数组开小了,一气之下开大好几倍
 * 超时N次,把cin 换成 scanf就过了
 * */
#include <iostream>
#include <cstdio>
#define MAX_N 500000
using namespace std;

int par[MAX_N];
int N, K;
int ans = 0;
void init(int n) {
    for (int i = 1; i <= n*3; i++) {
    par[i] = i;
    }
}

int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
}

void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) {
    par[px] = py;
    }
}

int main() {
    int T, X, Y;
    cin >> N >> K;
    init(3 * N);
    for (int i = 0; i < K; i++) {
    scanf("%d%d%d", &T, &X, &Y);
    if (X <= 0 || N < X || Y <= 0 || N < Y) {
        ans++;
        continue;
    }
    if (T == 1) {
        if (find(X) == find(Y + N) || find(X) == find(Y + 2 * N)) {
        ans++;
        continue;
        }
        else {
        unite(X, Y);
        unite(X + N, Y + N);
        unite(X + 2 * N, Y + 2 * N);
        }
    }
    else {
        if (find(X) == find(Y) || find(X) == find(Y + 2 * N)) {
        ans++;
        continue;
        }
        else {
        unite(X, Y + N);
        unite(X + N, Y + 2 * N);
        unite(X + 2 * N, Y);
        }
    }
    }
    cout << ans << endl;
    return 0;
}

---------------------

本文来自 yoer77 的**** 博客 ，全文地址请点击：https://blog.****.net/yoer77/article/details/62882150?utm_source=copy 
```
习题 https://vjudge.net/contest/264760#problem/M
这种种类并查集的，直接把两种情况全考虑进去。
https://blog.****.net/c___c18/article/details/83032936
Background
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.
Input
The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.
Output
The 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 experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong.
Sample Input
```
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4
```
Sample Output
```
Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!
```
Hint
Huge input,scanf is recommended.
题目意思就是看这些虫是不是gay，输入两个表示不同性别，看后面有没有冲突的

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

typedef pair<int, int> pii;
const int maxm = 2e3 + 5;
int pa[maxm * 2], rak[maxm * 2];

void make_set(int x){
    pa[x] = x;
    rak[x] = 0;
}

int findx(int x)
{
    int r = x, temp;
    while(pa[r] != r) r = pa[r];
    while(x != r)
    {
        temp = pa[x];
        pa[x] = r;
        x = temp;
    }
    return x;
}
void unio(int x, int y) {
x = findx(x);
y = findx(y);
if(x == y)return;
if(rak[x] > rak[y]) {
    pa[y] = x;
}
else {
    pa[x] = y;
    if(rak[x] == rak[y]) {
        rak[y]++;
    }
}
}
int n, m, x, y, t;
int main() {
scanf("%d", &t);
for(int i = 1; i <= t; i++) {
    scanf("%d%d", &n, &m);
    int flag = 0;
    memset(rak, 0, sizeof(rak));
    memset(pa, 0, sizeof(pa));
    for(int j = 1; j <= n * 2; j++) {
        make_set(j);
    }
    while(m--) {
        scanf("%d%d", &x, &y);
        if(findx(x) == findx(y)) {
            flag = 1;
        }
        else {
            unio(x + n, y);//1-n为一类，n + 1 - 2 * n为一类，把两种情况全考虑进去。
            unio(x, y + n);
        }
    }
    if(flag) printf("Scenario #%d:
Suspicious bugs found!

", i);
    else printf("Scenario #%d:
No suspicious bugs found!

", i);

}

return 0;
}

https://blog.****.net/shuangde800/article/details/8022068

https://blog.****.net/gemire/article/details/20566907
http://www.cnblogs.com/xzxl/p/7341536.html
https://blog.****.net/major_zhang/article/details/52138188

题目地址：https://vjudge.net/contest/280900#problem/M

题意：共n个数，p个操作。输入p。有两个操作M和C。M x y表示把x所在的栈放到y所在的栈上（比如M 2 6:[2 4]放到[1 6]上为[2 4 1 6]）,C x为输出x下面有几个数。

思路：并查集每个集合以栈最下面的数为根，维护两个数组num[x]表示x所在集合节点总数，count[x]表示x下方节点个数。每次查找压缩路径的时候更新count（换父节点的时候每轮都把父节点的count加给儿子，就可以一直更新到x所在栈的最底下），合并的时候更新px的count和py的num（把x的栈放到y的栈上，x下面多了num[y]个节点，新栈总根y总数增加num[x]个）。【不管是M还是C，先found一下x，把x的fa[x]更新到栈的最底下，count[x]才是真正的数！】

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;

const int maxm = 30005;
int pa[maxm], rak[maxm], tot[maxm];//tot总的数量，rak下面的数量

void make_set(int x) {
    pa[x] = x;
    rak[x] = 0;
    tot[x] = 1;
}


int findx(int a)
{
    if(a == pa[a])
        return a;

    int t = findx(pa[a]);
    rak[a] += rak[pa[a]];
    pa[a] = t;

    return pa[a];
}//因为是那爹的数量加上，所以这个压缩写法比较好，而不是加上祖先的。

void unio(int x, int y)
{
    x = findx(x);
    y = findx(y);
    if(x == y)return ;
//    if(rak[x] > rak[y])/*让rank比较高的作为父结点*/
//    {
//        pa[y] = x;
//        num[x] += num[y];
//    }
//    else
//    {
//        pa[x] = y;
//        if(rak[x] == rak[y])
//            rak[y]++;
//        num[y] += num[x];
//    }
    pa[x] = y;
    rak[x] = tot[y];
    tot[y] += tot[x];
//    printf("%d
", rak[x]);
}
int n, x, y;
char ch[3];
int main() {
scanf("%d", &n);
for(int i = 1; i <= 30000; i++) {
    make_set(i);
}
while(n--) {
    scanf("%s", ch);
    if(ch[0] == 'M') {
        scanf("%d%d", &x, &y);
        unio(x, y);
    }
    else if(ch[0] == 'C') {
        scanf("%d", &x);
        findx(x);//注意这里还要压缩一下
        printf("%d
", rak[x]);
    }
}
return 0;
}

题目地址：https://vjudge.net/contest/280900#problem/M

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;

const int maxm = 30005;
int pa[maxm], rak[maxm], tot[maxm];//tot总的数量，rak下面的数量

void make_set(int x) {
    pa[x] = x;
    rak[x] = 0;
    tot[x] = 1;
}


int findx(int a)
{
    if(a == pa[a])
        return a;

    int t = findx(pa[a]);
    rak[a] += rak[pa[a]];
    pa[a] = t;

    return pa[a];
}//因为是那爹的数量加上，所以这个压缩写法比较好，而不是加上祖先的。

void unio(int x, int y)
{
    x = findx(x);
    y = findx(y);
    if(x == y)return ;
//    if(rak[x] > rak[y])/*让rank比较高的作为父结点*/
//    {
//        pa[y] = x;
//        num[x] += num[y];
//    }
//    else
//    {
//        pa[x] = y;
//        if(rak[x] == rak[y])
//            rak[y]++;
//        num[y] += num[x];
//    }
    pa[x] = y;
    rak[x] = tot[y];
    tot[y] += tot[x];
//    printf("%d
", rak[x]);
}
int n, x, y;
char ch[3];
int main() {
scanf("%d", &n);
for(int i = 1; i <= 30000; i++) {
    make_set(i);
}
while(n--) {
    scanf("%s", ch);
    if(ch[0] == 'M') {
        scanf("%d%d", &x, &y);
        unio(x, y);
    }
    else if(ch[0] == 'C') {
        scanf("%d", &x);
        findx(x);//注意这里还要压缩一下
        printf("%d
", rak[x]);
    }
}
return 0;
}

并查集 poj1988 Cube Stacking（并查集

相关推荐