(a) common and search set

A normal parallel lookup set consists of three parts: (1) an array of integers (2) an initialization function, inin (3) a lookup function, find (4) a merge function, join — >1.1 initialization, inin makes each element itself a collection, i.e. Pre [I]= I.

 void inin(int x)		/ / initialization
{
	int i;
	for (i = 0; i <= x; i++)
	{
		pre[i] = i;
		rank1[i] = 1; }}Copy the code

– >1.2 Find function, find to find the root node of an element.

 int find(int x)
{
	int r;
	r = x;
	while(r ! = pre[r])// Its node is not itself.
	{
		r = pre[r];
	}
	return r;             // return the root node
}
Copy the code

– >1.3 Merge function. Join merges the root nodes of two elements to form a tree

void join(int a, int b)
{
	int fa;
	int fb;
	fa = find(a);		// find the following node of a
	fb = find(b);		// find the following node of b
	if(fa ! = fb)// When a and B root nodes are different, merge them{ pre[fa] = fb; }}Copy the code

Here, we will find that after the implementation of the code above, the formation of the depth of the tree may be too big, a word the tailback is likely, this search efficiency is very low, of course, in some questions, the data volume is small, efficiency is doesn’t matter, but in some topic is a large amount of data, the efficiency is very important. And the trees that form may degrade. To avoid this problem, let’s make some code improvements.

Compression path:

This means that all nodes point to the root node, so that the number of layers of the tree is maintained at a low level, so as to improve the search efficiency.



Code implementation:

#define N 55005
int pre[N];			// The node of the tree
int rank1[N];		// Tree depth
int n, m;
void inin(int x)		/ / initialization
{
	int i;
	for (i = 0; i <= x; i++)
	{
		pre[i] = i;
		rank1[i] = 1; }}int find(int x)		 // find the root of node x
{
	if (pre[x] == x)
	{				 // Recursive exit: the parent of x is x itself, that is, x is the root
		return x;
	}
	else
		return pre[x] = find(pre[x]);   // Recursively looking for this code is equivalent to finding the root rootx, and then pre[x]=rootx
}

void join(int a, int b)		// Node and union
{
	int fa;
	int fb;
	fa = find(a);
	fb = find(b);
	if (fa == fb)
		return ;
	else if (rank1[fa] > rank1[fb])
	{
		pre[fb] = fa;
	}
	else
	{
		if(rank1[fa] == rank1[fb]) { rank1[fb]++; } pre[fa] = fb; }}Copy the code

Examples:

To avoid offending the people who live in different parts of the delta, who have their own totems, the leaders now want to know how many they might have. But that would be boring for them, so now it’s up to you. When you see people in two regions worshiping stone statues of the same appearance, you can tell that they have the same totem. Given that there are n(n <= 50000) areas in the delta, you see the m(M <= N (n-1)/2) group of people worming the same stone statues, now may I ask how many totems they have at most?

Input has multiple groups of data. For each set of data: First line: two integers n and m. The following m lines: Each line contains two integers I and j, indicating that you find people in region I and region J worshipping the same stone statue. The area number ranges from 1 to N. In the last line of the input,n = m = 0.

Output For each set of test data, Output one line, Output data sequence number (starting at 1) and the maximum number of totems. (See sample)

Sample Input

10 9

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

1 10

10 4

2 3

4 5

4 8

5 8

0 0

Sample Output

Case 1: 1

Case 2: 7

#include<iostream>
#include<cstdio>
using namespace std;
#define N 55005
int pre[N];			// The node of the tree
int rank1[N];		// Tree depth
int n, m;
int sum;
void inin(int x)		/ / initialization
{
	int i;
	for (i = 0; i <= x; i++)
	{
		pre[i] = i;
		rank1[i] = 1; }}int find(int x)		 // find the root of node x
{
	if (pre[x] == x)
	{				 // Recursive exit: the parent of x is x itself, that is, x is the root
		return x;
	}
	else
		return pre[x] = find(pre[x]);   // Recursively looking for this code is equivalent to finding the root rootx, and then pre[x]=rootx
}

void join(int a, int b)		// Node and union
{
	int fa;
	int fb;
	fa = find(a);
	fb = find(b);
	if (fa == fb)
		return ;
	else if (rank1[fa] > rank1[fb])
	{
		pre[fb] = fa;
		sum--;
	}
	else
	{
		if(rank1[fa] == rank1[fb]) { rank1[fb]++; } pre[fa] = fb; sum--; }}int main(a)
{
	
	int a, b;
	int k=0;
	while (cin >> n >> m&&n&&m)
	{
		k++;
		inin(n);
		sum = n;
		while (m--)
		{
			cin >> a >> b;
			join(a, b);
		}
		cout << "Case ";
		cout << k << ':';
		cout <<""<< sum << endl;
	}
	return 0;
}
Copy the code



And check the use of set algorithm;

1. Maintain the connectivity of undirected graphs. Support for determining whether two points are in the same connected block and whether adding an edge creates a ring.

2. Used in the Kruskal algorithm for solving the minimum spanning tree.

The following is the big guy and check the set of explanation:

Common parallel lookup set