FUCKING CRAZY! The food chain is so hard

and check

process quickly

1. Merge two sets
2. Ask if two elements are in a set

For example belong[x] stores which collection x belongs to, for example belong[x] = a means element x belongs to collection a

Then we can use O(1) to determine whether the elements x and y are in the same set

if(belong[x] == belong[y])

But if we want to merge a set of 1000 elements and a set of 2000 elements, then we have to do at least 1000 operations

But union-find can do both operations in nearly O(1) time

Fundamental

Maintain each collection in the form of a tree

The root node element (root) of each collection is her representative element, and the number of the root node is the number of my current collection

For each point, we store who her parent is, p[x] is his parent, p[p4] = p1

When we ask which set a certain point belongs to, for example to find which set p4 belongs to, we can search up according to his father until the root node

//Question 1 How to determine the root of a tree
if(p[x] == x)
//Question 2 How to find the set number of x
while(p[x]!=x)
{
    x = p[x];
}
//Question 3 How to merge two sets, add an edge: px is the set number of x, py is the set number of y
p[x] = y;

Compression path optimization

When we query which set an element pp4 is in, we store all the points on his path under the root node

template

(1)Simple union lookup:

    int p[N]; //store the ancestor node of each point

    // Returns the ancestor node of x
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // Initialization, assuming the node number is 1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // Merge the two sets that a and b are in:
    p[find(a)] = find(b);


(2)maintain size The union lookup set:

    int p[N], size[N];
    //p[] stores the ancestor node of each point, size[] is only meaningful for the ancestor node, indicating the number of points in the set where the ancestor node is located

    // Returns the ancestor node of x
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // Initialization, assuming the node number is 1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // Merge the two sets that a and b are in:
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)Maintain a union of distances to ancestor nodes:

    int p[N], d[N];
    //p[] stores the ancestor node of each point, d[x] stores the distance from x to p[x]

    // Returns the ancestor node of x
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // Initialization, assuming the node number is 1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // Merge the two sets that a and b are in:
    p[find(a)] = find(b);
    d[find(a)] = distance; // According to the specific problem, initialize the offset of find(a)

practise

836. Merge Collections - AcWing Question Bank

There are a total of n numbers, numbered 1∼n, and each number is in a set at first.

Now there are m operations to be performed, and there are two types of operations:

1. M a b, merge the sets where the two numbers numbered a and b are located. If the two numbers are already in the same set, this operation is ignored;
2. Q a b, asking whether the two numbers numbered a and b are in the same set;

input format

Enter the integers n and m on the first line.

The next m lines, each line contains an operation instruction, the instruction is one of M a b or Q a b.

output format

For each query command Q a b, output a result, if a and b are in the same set, output Yes, otherwise output No.

One line for each result.

data range

1≤n,m≤105

Input sample:

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

Sample output:

Yes
No
Yes

#include<iostream>

using namespace std;

const int N = 100010;
int n,m;
int p[N];

int find(int x) //Returns the ancestors of x
{
    if(p[x]!=x)
    {
        p[x] = find(p[x]);
    }
    return p[x];
}     

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n >> m;
    
    for(int i = 1;i <= n ;i++)
    {
        p[i] = i;
    }
    
    while(m--)
    {
        char op;
        int a,b;
        cin >> op >> a >> b;
        if(op == 'M')
        {
            p[find(a)] = find(b);
        }else if(op == 'Q'){
            if(find(a) == find(b))
            {
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
    }
    return 0;
}

837. Number of Midpoints in Connected Blocks - AcWing Question Bank

Given an undirected graph containing n points (numbered 1∼n), initially the graph has no edges.

Now there are m operations to be performed, and there are three types of operations:

1. C a b, connecting an edge between point a and point b, a and b may be equal;
2. Q1 a b, ask if point a and point b are in the same connected block, a and b may be equal;
3. Q2 a, the number of points in the connected block where point a is located;

input format

Enter the integers n and m on the first line.

The next m lines, each containing an operation instruction, one of C a b, Q1 a b, or Q2 a.

output format

For each query instruction Q1 a b, if aa and bb are in the same connected block, output Yes, otherwise output No.

For each query command Q2 a, output an integer representing the number of points in the connected block where point a is located

One line for each result.

data range

1≤n,m≤105

Input sample:

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

Sample output:

Yes
2
3

Connected block: If you can walk from point a to b and from b to a, then a and b belong to the same connected block

We can use sets to maintain connected blocks. When we connect an edge between two connected blocks, we actually merge the two sets.

#include<iostream>

using namespace std;

const int N = 100010;
int n,m;
int p[N];
int Size[N];

int find(int x) //Returns the ancestors of x
{
    if(p[x]!=x)
    {
        p[x] = find(p[x]);
    }
    return p[x];
}     

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n >> m;
    
    for(int i = 1;i <= n ;i++)
    {
        p[i] = i;
        Size[i] = 1;
    }
    
    while(m--)
    {
        char op[5];
        int a,b;
        cin >> op;
        if(op[0] == 'C')
        {
            cin >> a >> b;
            if(find(a) == find(b))
            {
                continue;
            }
            Size[find(b)] += Size[find(a)];
            p[find(a)] = find(b);
        }else if(op[1] == '1'){
            cin >> a >> b;
            if(find(a) == find(b))
            {
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }else{
            cin >> a;
            cout << Size[find(a)] << endl;
        }
    }
    return 0;
}

240. Food Chain - AcWing Question Bank

There are three types of animals in the animal kingdom. A, B, and C form an interesting loop of food chains.

A eats B, B eats C, and C eats A.

There are N animals, numbered 1∼N.

Every animal is one of A, B, and C, but we don't know which one it is.

Some people describe the food chain relationship formed by these N animals in two ways:

The first statement is 1 X Y, which means that X and Y are the same kind.

The second statement is 2 X Y, which means that X eats Y.

This person uses the above two statements to say KK sentences sentence after sentence to NN animals. Some of these KK sentences are true and some are false.

When a sentence satisfies one of the following three conditions, the sentence is false, otherwise it is true.

1. The current words conflict with some previous true words, which are false words;
2. If X or Y is larger than N in the current word, it is a lie;
3. The current word means that X eats X, which is a lie.

Your task is to output the total number of falsehoods given N and K sentences.

input format

The first line is two integers N and K, separated by a space.

Each of the following K lines is three positive integers D, X and Y separated by a space, where D represents the type of argument.

If D=1, it means that X and Y are the same.

If D=2, it means that X eats Y.

output format

There is only one integer, representing the number of falsehoods.

data range

1≤N≤50000
0≤K≤100000

Input sample:

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

We implement the food chain by maintaining and checking the distance from the child nodes to the root node

For example, the distance from 1 to the root node is 1, indicating that 1 is eaten by the root, and the distance from 4 to the root is 1, indicating that 4 is eaten by the root

The distance from 2 to the root is 2, indicating that 2 is eaten by the node with a distance of 1 to the root

The distance from 3 to the root is 3, indicating that 3 is eaten by the node with a distance of 2 to the root, and can eat the node with a distance of 1 from the root.

#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]);
        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)
            {
                if (px == py && (d[x] - d[y]) % 3) res ++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}