Let's take a look at the definition given by Du Niang:

And look up the set. In some set application problems with N elements, we usually make each element form a single element set at the beginning, and then merge the sets of elements belonging to the same group in a certain order. In the meantime, we should repeatedly find out which set an element is in. In recent years, such problems have repeatedly appeared in the international and domestic competitions of informatics. Its characteristic is that it does not seem complex, but the amount of data is huge. If it is described with normal data structure, it is often too large in space for the computer to bear; Even if we barely pass in space, the running time complexity is also very high. It is impossible to calculate the results required by the test questions within the running time specified in the competition (1 ~ 3 seconds), which can only be described by parallel search.

To sum up:

If we have a large set of elements, we need to call the following two operations frequently:

- Merge two element intervals
- Determine whether two elements are in a set

If we don't have a search set, the time complexity of performing these two operations will be very high in the face of a large amount of data

If we use the structure of parallel query set, although the time complexity of a single operation may be O(n), if we call these two functions frequently, the average time complexity can reach O(1)

We don't prove this conclusion. (after all, the big guys have proved it for more than 20 years. How can I prove it in such a short time (whisper))

Cough, in a word, just remember the above conclusion

This structure can solve some problems that need to count the number of sets

# Implementation of parallel search set

Give a definition first:

The pointer points to its own node. We call it the representative node of the set. It exists as the most vertex (parent node) identifying the set

If we have an integer array, we need to implement it into a union search set

When we initialize, we first treat each element as a separate set

That is to point out a pointer to yourself

This completes our initialization, that is, the representative node of each element is itself

Therefore, it is very simple for us to judge whether the elements come from the same set. We can directly judge whether their representative nodes are the same

The operations of merging are as follows:

In this case, if we want to merge the set of 1 and 2 elements, we can hang the parent node of one element set on another parent node

We might as well hang 2 on 1

In this way, we have completed an element merging

If we want to merge 2 and 3 this time, what should we do?

Similarly, just hang the parent node of one set to the parent node of another element

However, in this case, it should be noted that in order to speed up efficiency, we usually hang the parent node of a small set on the parent node of a large set

Like this

But in this process, we still need some operations

For example, how to find the representative node of the set where an element is located? How to quickly find representative nodes? It is described in detail in the following code implementation

We need the following structure to implement:

An array that records the subscript position of the key node of an element, the size of the set where the current element is located, and the number of the current set

vector<int>parent;//Record the key node at this position, such as parent[i]=a, and the element representing the I subscript is at a vector<int>size;//Record the size of the set of key nodes. It is only valid for key nodes, and set non key nodes to 0 vector<int>help;//Auxiliary array, which will be introduced later int sets;//Record the number of current query sets

During initialization, we need to know and check the number of elements in the initial set. According to the setting that each element has a set in the initial set, we can quickly write the following initialization code:

int n = nums.size();//How many elements are there in our array, and how many sets are opened initially parent.resize(n); size.resize(n); help.resize(n); sets = n; for (int i = 0; i < n; i++) { parent[i] = i;//Key nodes for themselves size[i] = 1;//The collection size is 1 }

Because in the above operation, you need to frequently find the location of key nodes, so you also need to implement a function to find the location of key nodes

The principle is simple:

If the subscript of the parent[i] record of an element is not the subscript of the element itself, it means that the node is not the representative node. We find the subscript through the position of the parent array record and iterate until the key node is found

//This function finally returns the representative node subscript of the element in the current subscript int findfather(int i) { while (i != parent[i]) { i = parent[i]; } return i; }

But in some extreme cases, if such frequent calls occur, the time complexity of each call is O(n)

For example, the elements are all on a chain, forming a structure similar to a linked list. We can find it from the lowest element

If we don't do any optimization, the average time complexity is O(n)

We can optimize the compression path:

The specific implementation is as follows:

Every time we traverse the array, we put the following elements in the help

Then compress the path. We pop up each element in help in turn, and then set the representative node of each element as the current return value

In this way, each element points to a unique representative node

Summary:

The help array mentioned earlier is used here as a stack

Although the time complexity of a single search may be O(n), after our path compression, if we repeatedly search the elements in this set in the future, the time complexity will be O(1)

Because our premise is a large number of repeated operations, the average time complexity is O(1)

Complete search representative node code:

int findfather(int i) { int hi = 0; while (i != parent[i]) { help[hi++] = i; i = parent[i]; } for (hi--; hi >= 0; hi--)//Remember first-- { parent[help[hi]] = i;//Path compression operation help[hi] = 0; } return i; }

Next, let's implement the two methods mentioned at the beginning of the article

Note: when we use these two methods, the parameters are passed to the subscript in the original array

It's easy to find out whether they are the same elements. You can directly judge whether they are equal

bool isSameFather(int i, int j) { return findfather(i) == findfather(j); }

The operations during merging are as follows:

First, find out the representative nodes of the set where the elements are located

int A = findfather(i); int B = findfather(j);

At this time, judge that if A=B, it means that the two elements come from the same set, there is no need to merge. Just exit the function directly

Because we hang a small set on a large set, we need to judge which of a and B is a large set

int big = size[A] >= size[B] ? A : B; int small = big == A ? B : A;

Then perform the merge operation: change the position of the representative node, change the size value, change the number of sets, etc

parent[small] = big; size[big] += size[small]; size[small] = 0; sets--;//Merging one represents that there is one less set in the query set

In most cases, we may also need to return and check the number of elements in the set

int getSets() { return sets; }

The complete code is as follows

class Union2 { public: Union2(vector<int>& nums) { int n = nums.size(); parent.resize(n); size.resize(n); help.resize(n); sets = n; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } bool isSameFather(int i, int j) { return findfather(i) == findfather(j); } int getSets() { return sets; } void together(int i, int j)//It's a subscript { int A = findfather(i); int B = findfather(j); if (A != B) { int big = size[A] >= size[B] ? A : B; int small = big == A ? B : A; parent[small] = big; size[big] += size[small]; size[small] = 0; sets--; } } private: vector<int>parent;//Record the key nodes at this location vector<int>size;//Record the location of key nodes vector<int>help;//Make stack int sets;//Number of record sets int findfather(int i) { int hi = 0; while (i != parent[i]) { help[hi++] = i; i = parent[i]; } for (hi--; hi >= 0; hi--)//Remember first-- { parent[help[hi]] = i; help[hi] = 0; } return i; } };

In addition, add the implementation of hash table, and save the hash as a pointer node. Everything else is the same

class Node { public: Node(int x) :val(x) {} private: int val; }; class Union { private: unordered_map<int, Node*>node;//Value and node corresponding to value unordered_map<Node*, Node*>parent;//Node and its representative node unordered_map<Node*, int>size;//Represents a node and its corresponding set size Node* findfather(Node* n) { stack<Node*>path; Node* cur = n; while (parent[cur] != cur) { cur = parent[cur]; path.push(cur); } if (!path.empty()) { Node* now = path.top(); parent[now] = cur; path.pop(); } return cur; } public: Union(vector<int>& nums) { for (auto i:nums) { Node* n = new Node(i); node[i] = n; parent[n] = n; size[n] = 1; } } bool isSameUnion(int a, int b) { return findfather(node[a]) == findfather(node[b]); } int setsize() { return size.size(); } void together(int a, int b) { Node* A = findfather(node[a]); Node* B = findfather(node[b]); if (A != B) { Node* big = size[A] >= size[B] ? A : B; Node* small = A == big ? B : A; parent[small] = big; size[big] += size[small]; size.erase(small); } } };

# Parallel search set application

## Force deduction 547, number of provinces

Title Description:

There are n cities, some of which are connected to each other, others are not connected. If city a is directly connected to city b and city b is directly connected to City c, city a is indirectly connected to city c.

A province is a group of directly or indirectly connected cities, excluding other cities that are not connected.

Give you an n x n matrix isConnected, where isConnected[i][j] = 1 indicates that the ith city and the jth city are directly connected, and isConnected[i][j] = 0 indicates that they are not directly connected.

Returns the number of provinces in the matrix.

For example: Enter: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output: 2 (because 1 and 2 cities are connected, one of 1 and 2 is not the capital)

Solution ideas:

This problem is a typical problem of the number of sets returned by merging and searching sets

If there are three cities of 0, 1 and 2, let 0, 1 and 2 respectively represent the horizontal and vertical coordinates in the array. If there are roads between them, set their intersection in the array as 1, and vice versa as 0

We can get the following properties of the array: the elements on the diagonal are always 1, because they must be related to themselves

This array must be a symmetric matrix. If there is a connection between (1,2), then there must be a connection between (2,1)

Therefore, when traversing, we only need to traverse the elements above the diagonal of the array

Because there are several cities in the initial row, when we initialize and query the set, we only need to transfer the size. Initially, each city is the capital, that is, each node is a representative node

If there is a connection, merge the two cities

The code is as follows:

class Union//Union search set { public: Union(int n)//As many cities as there are, it is initially assumed that each city is the capital { parent.resize(n); size.resize(n); help.resize(n); set=n; for(int i=0;i<n;i++) { parent[i]=i;//The initial parent node points to itself size[i]=1;//Each collection has only one element } } bool isSameFather(int i,int j)//Observe whether it belongs to the same element { return findFather(i)==findFather(j); } void together(int i,int j)//Merge a collection of two elements { int A=findFather(i); int B=findFather(j);//Find their representative nodes first if(A!=B)//Unequal operation { //In order to improve efficiency, hang the small collection under the large collection int big=A>=B?A:B; int small=big==A?B:A; parent[small]=big;//Change the representative node size[big]+=size[small]; size[small]=0; set--; } } int getSet() { return set; } private: vector<int>parent;//Where is the father of a subscript position vector<int>size;//Represents the number of sets representing nodes vector<int>help;//Used as a stack when compressing paths int set;//Number of record sets int findFather(int i)//Pass in the subscript and return the subscript representing the node { int hi=0; while(parent[i]!=i)//Judge whether the father of the element is himself, stop or iterate { help[hi++]=i; i=parent[i]; } //Path compression for(hi--;hi>=0;hi--) { parent[help[hi]]=i; help[hi]=0; } return i; } }; class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int n=isConnected.size(); Union u(n); for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++)//You only need to traverse the elements in the upper right corner { if(isConnected[i][j]==1) { u.together(i,j); } } } return u.getSet(); } };

## Force deduction 200, number of islands

Give you a two-dimensional grid composed of '1' (land) and '0' (water). Please calculate the number of islands in the grid.

Islands are always surrounded by water, and each island can only be formed by adjacent land connections in the horizontal and / or vertical direction.

In addition, you can assume that all four sides of the mesh are surrounded by water.

For example:

Input: grid =[

["1","1","0","0","0"],

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]

]

Output: 3

Thinking solution

This problem actually has a recursive infection method, but it is not the focus of this chapter, so I only post the code and don't explain it in detail

class Solution { public: void infect(vector<vector<char>>& grid,int r,int c) { //In order to prevent dead recursion during infection, the numbers are changed to 2 if(r<0||c<0||r>=grid.size()||c>=grid[0].size()||grid[r][c]!='1') { return; } grid[r][c]='2'; infect(grid,r-1,c); infect(grid,r+1,c); infect(grid,r,c-1); infect(grid,r,c+1); } int numIslands(vector<vector<char>>& grid) { //Recursive infection method int ans=0; int r=grid.size(); int c=grid[0].size(); for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { if(grid[i][j]=='1') { ans++; infect(grid,i,j); } } } return ans; } };

Let's focus on the implementation method of this problem

First of all, let's have an array of row s and columns when we initialize the colrow

We can convert two-dimensional coordinates into one-dimensional array. The conversion formula is as follows:

int index(int i,int j) { return i*col+j; }

At the beginning, we first traverse the whole map. As long as there is an island, we initialize its corresponding coordinates. At the beginning, each 1 is regarded as an independent island

In order to prevent missing numbers, when we traverse, observe whether there are islands in the upper left position of the course position, and merge if there are

int index(vector<vector<char>>& grid,int i,int j) { return i*grid[0].size()+j; } class Union2 { public: Union2(vector<vector<char>>& grid) { //Pay special attention to this problem and look up the structure of the set //Convert the parallel search set into a one-dimensional array, store elements in the corresponding position of the subscript of the two-dimensional array, and do not process others. Only when traversing each 1 can the corresponding position of the parallel search set be processed int n=grid.size()*grid[0].size(); parent.resize(n); size.resize(n); help.resize(n); sets=0; for(int i=0;i<grid.size();i++) { for(int j=0;j<grid[0].size();j++) { if(grid[i][j]=='1') { int k=index(grid,i,j); parent[k]=k; size[k]++; sets++;//The number of sets increases dynamically } } } } bool isSameFather(int i, int j) { return findfather(i) == findfather(j); } int getSets() { return sets; } void together(int i, int j)//It's a subscript { int A = findfather(i); int B = findfather(j); if (A != B) { int big = size[A] >= size[B] ? A : B; int small = big == A ? B : A; parent[small] = big; size[big] += size[small]; size[small] = 0; sets--; } } private: vector<int>parent;//Record the key nodes at this location vector<int>size;//Record the location of key nodes vector<int>help;//Make stack int sets;//Number of record sets int findfather(int i) { int hi = 0; while (i != parent[i]) { help[hi++] = i; i = parent[i]; } for (hi--; hi >= 0; hi--)//Remember first-- { parent[help[hi]] = i; help[hi] = 0; } return i; } }; class Solution { public: int numIslands(vector<vector<char>>& grid) { Union2 u(grid); for(int j=1;j<grid[0].size();j++) { if(grid[0][j-1]=='1'&&grid[0][j]=='1') { u.together(index(grid,0,j-1),index(grid,0,j)); } } for(int i=1;i<grid.size();i++) { if(grid[i-1][0]=='1'&&grid[i][0]=='1') { u.together(index(grid,i-1,0),index(grid,i,0)); } } //The first two for loops deal with boundaries for(int i=1;i<grid.size();i++) { for(int j=1;j<grid[0].size();j++) { if(grid[i][j]=='1') { if(grid[i-1][j]=='1') { u.together(index(grid,i-1,j),index(grid,i,j)); } if(grid[i][j-1]=='1') { u.together(index(grid,i,j),index(grid,i,j-1)); } } } } return u.getSets(); } };