Connected Block & food chain - (summary of parallel search set)

Catalog

1、 And search the three most basic processes

2、 And the main operation of the search set

3、 Example （1） Here we go —— The number of connected blocks

4、 Example （2） Here we go —— The food chain （ Take the right and check the collection ）

5、 Analysis of weighted union search set based on food chain

---

1、 And search the three most basic processes

One 、 Merge the two sets ;

Two 、 Ask if two elements are in the same set ;

3、 ... and 、 The number of elements in a set ;

2、 And the main operation of the search set

  One 、 Looking for ancestral nodes （ Path optimization ）;

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);// Path optimization 
    // Find directly through path optimization X Our ancestors 
    return p[x];
    //while(x!=p[x]) x=p[x];   Basic version 
    // It may not be good because the depth of the tree is too deep , It takes a lot of time 
}

Two 、 Merge a、b Combine the two sets to calculate the number of elements （ There are fallible points ！！！）

int x = find(a), y = find(b); 
if (x != y)
{
   p[x] = y;
   s[x] += s[y]; // Perform consolidation to calculate the number of elements in the set 
}

// The following is the wrong version 
if(find(a) != find(b))
{
   p[find(a)] = find(b);
   s[find(b)] += s[find(a)];
}
// These two look the same , There's no difference , But think about it , But there's something else 
// The following is wrong , It's easy to get dizzy 

Fine products ！！！ I was stuck here for a long time , Leng doesn't know what's wrong . It needs to be thought out carefully ！

The second case above ：p[find(a)] = find(b) after ,a and b The root node of is the same ,find(a) == find(b)（ The original find(a) Vanished ）,s[find(b)] += s[find(a)] It is equivalent to s[find(b)] *= 2, At this time, there is confusion . It's equivalent to putting    s[find(b)] += s[find(a)] Put it in front , hold p[find(a)] = find(b) Just put it in the back .

The first case above ：p[a] = find(b) after ,a == find(a),b == find(b), Now the original find(a) still , therefore s[b] += s[a] The addition is still the original s[find(a)].

3、 Example （1） Here we go —— The number of connected blocks

Title Description

Given an inclusion n A little bit （ The number is 1~n ） Undirected graph of , Initially, there are no edges in the graph .
Now it's time to m Operations , There are three kinds of operations ：

1. C a b, At point a Sum point b One edge between them ,a and b May be equal ;
2. Q1 a b, Inquiry point a Sum point b Whether in the same connected block ,a and b May be equal ;
3. Q2 a, Inquiry point a The number of points in the connected block .

Input format

Enter an integer in the first line n and m.
Next m That's ok , Each line contains an operation instruction , Instructions for C a b ,Q1 a b or Q2 a One of the .

Output format

For each inquiry command Q1 a b, If a and b In the same connecting block , The output Yes, Otherwise output No.
For each inquiry instruction Q2 a, Output an integer to represent the point a The number of midpoint in the connected block .
Each result takes up one line

Data range

1 <= n,m <= 1e5

The sample input

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

Sample output

Yes
2
3

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1e6 + 10;
int n, m, p[N], s[N];

int find(int x)
{
	if (x != p[x]) p[x] = find(p[x]);// Path optimization 
	return p[x];
}
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) p[i] = i, s[i] = 1;
	while (m--)
	{
		char op[2];
		int a, b;
		scanf("%s", &op);
		if (op[0] == 'C')
		{
			scanf("%d %d", &a, &b);
			if (find(a) != find(b))// Pay attention ！ It's easy to get wrong ！！
			{
				s[find(b)] += s[find(a)];// First recognize your relatives 
				p[find(a)] = find(b);// And change our ancestors 
			}
		}
		if (op[1] == '1')
		{
			scanf("%d %d", &a, &b);
			if (find(a) == find(b)) printf("Yes\n");
			else printf("No\n");
		}
		if (op[1] == '2')
		{
			scanf("%d", &a);
			printf("%d\n", s[find(a)]);
		}
	}
	return 0;
}

4、 Example （2） Here we go —— The food chain （ Take the right and check the collection ）

Title Description

There are three kinds of animals in the animal kingdom A、B、C, The food chain of these three kinds of animals forms an interesting ring .
A eat B,B eat C,C eat A.
existing N Animals , With 1~N Number .
Every animal is A,B,C One of the , But we don't know which one it is .
There are two ways of saying it N Describe the food chain of animals ：
The first is 1 X Y , Express X and Y It's the same kind .
The second is 2 X Y , Express X eat Y.
This man is right N Animals , Use the two statements above , Say... Sentence by sentence K Sentence , this K Some sentences are true , Some are fake .
When a sentence satisfies one of the following three , This is a lie , Otherwise, it's the truth .

1. The current words conflict with some of the real words in front , It's a lie ;
2. In the current conversation X or Y Than N Big , It's a lie ;
3. The current words mean X eat X , It's a lie .

Your task is based on the given N and K Sentence , The total number of output lies .

Input format

The first line is two integers N and K, Separated by a space .
following K Each line is three integers D,X,Y, Separate the two numbers with a space , among D The type of statement .
if D = 1, said X and Y It's the same kind . There's only one whole number , The number of lies .
if D = 2, said X eat Y.

Output format

There's only one whole number , The number of lies

The 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

Data range

1 <= N <= 50000
0 <= K <= 100000

5、 Analysis of weighted union search set based on food chain

One 、 The idea of weighted and search set

As long as they are related , Belong to the same set , Just add them to the collection （ Whether homogeneous or heterogeneous ）, Therefore, the problem of the sideband weight of the joint search set is essentially to maintain a large set （ Others are single points , Then add them to the large collection one by one ）. Therefore, as long as two elements are in the same set , We can know the relationship between them through the distance between them and the root node （% modulus ）;

Two 、 About the order of recursive call and distance calculation

 Here are two different kinds of recursion （ At first glance , But there is a big difference ）
<1>int find(int x)
{
    if(p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}


 I was also thinking , The following operation seems to be simpler , But why is it always wrong 
<2>int find(int x)
{
    if(p[x] != x)
    {
        d[x] += d[p[x]];// The mistake is here p[x] On ( No path compression )
        p[x] = find(p[x]);
    }
    return p[x];
}

Cause analysis ：

1、 In the second recursive code d[x] At first it means x The distance from the parent node to , If there is no path compression , that d[p[x]] refer to p[x] The distance to its parent node , Then the practical meaning of the second recursion becomes ：d[x] = d[x] + d[p[x]]——x The distance to the root node = x The distance from the parent node to + Distance from parent node to parent node （ The mistake is here ） Because the parent node of the parent node is not necessarily the root node , Cause distance calculation error .

！！！

2、 In the first recursive code, path compression is carried out first （int t = find(p[x]）, then d[x] = d[x] + d[p[x]]—— It becomes ：x The distance to the root node = x The distance from the parent node to + Distance from parent node to root node , Only first find() function ,d[p[x]] Is the distance from the parent node to the root node . Not carried out find() is p[x] To p[p[x]] It's just a distance , Not to p[x] The distance between the root nodes of .

3、 ... and 、 About the calculation of food chain relationship （ come from y The general picture ）

1. When x and y It's the same kind of time （ It can be divided into two types: in a set and not in a set ）

2、. When x eat y When （ It can be divided into two types: in a set and not in a set ）

#include <iostream>
#include<algorithm>

using namespace std;

const int N = 50010;
int n, m;
int p[N], d[N];

int find(int x)
{
    if (p[x] != x)//  If x Not the root node 
    {
        //  This find After statement execution ,p[x] The distance to the root node has been updated .
        int t = find(p[x]);
        //x The distance to the root node  = x The distance from the parent node to  +  Distance from parent node to root node 
        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)// x and y It's the same kind 
            {
               
                if (px == py && (d[x] - d[y]) % 3!=0) res++; //  Pay attention to the skill of taking mold 
                else if (px != py)
                {
                    //  Merge into the same kind ,x Where the set is combined y In the set .
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else// x eat y
            {
                if (px == py && (d[x] - d[y] - 1) % 3!=0) res++;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}