C++

C++ – And check Luogu P3367

_Redstone_c_

It is used to quickly find which set a certain point is in. It is often used in questions about graphs. You can check Luogu P3367 question.

#include <cstdio>
#define _for(i, n) for(int i = 0; i < n; i++)
using namespace std;
const int MAXN = 1e6 + 100;
int m, n, o, x, y;
int map[MAXN];
int find(int u) {
    if(map[u] != u) map[u] = find(map[u]);
    return map[u];
}
int main() {
    scanf("%d %d", &m, &n);
    _for(i, n) map[i] = i;
    _for(i, n) {
        scanf("%d %d %d", &o, &x, &y);
        if(o == 1) map[find(x)] = find(y);
        else if(find(x) == find(y)) printf("Y\n");
        else printf("N\n");
    }
    return 0;
}

The above is the template code for union lookup, which is also Luogu's AC code. Its storage structure is a one-dimensional array called map. It stores the sets where different nodes are located. For example, map[1] = 1 means that node 1 is in set No. 1. element, where find is the main part of the union search set, and the parameter u represents the set number where node u is located.

First of all, let’s think about it from the perspective of never having any contact with and looking up sets. We can use the number of the node to indicate the set where the node is located. For example, initially let node 1 set at No. 1, node 2 at No. 2... Node N at No. N Set, then this question is divided into two parts, search and merge, so it needs to be operated from two angles, because search requires a storage solution, so here we study merger first. The method here is to let one node belong to another Under one node, for example, to merge node 1 and node 2, you can set map[1] = 2, so that nodes 1 and 2 belong to the same set. Then there is another problem at this time: if map[1] = 4, How to operate when map[2] = 3? So in the program we have to first find(1), find(2) and then directly merge their belonging sets, that is, let map[find(1)] = find(2), and finally the search part, directly judge Is find(x) equal to find(y) and then the output will be fine.

Then, if you do this, you will find that TLE!

This is because a problem may arise, that is, map[0] = 1, map[1] = 2, map[2] = 3, map[3] = 4, map[4] = 5, map[5] = 6... map[n – 1] = n, which will waste a lot of time in the search. The time complexity is O(n), which is far inferior to the following storage map[0] = n, map[1] = n, map[2] = n, map[3] = n, map[4] = n, map[5] = n... map[n – 1] = n, the time complexity is O(1), how to implement it? It is to shorten the path while searching during the find process, which is the top code.

Post Reply