Concurrent search set

A code explanation about the union search set

This article draws on the code of two big men
bosses

bosses

subject ：

4-3-1 Union checking set Circle of friends (25 branch )
A school has N A student , formation M A club . The students in each club have some similar interests , Form a circle of friends . A student can belong to several different clubs at the same time . according to “ My friend's friend is also my friend ” This inference leads to , If A and B It's a friend. , And B and C It's a friend. , be A and C It's also a friend . Please write a program to calculate how many people are in the biggest circle of friends .

Input format :
The first line of input contains two positive integers N（≤30000） and M（≤1000）, They represent the total number of students in the school and the number of clubs . hinder M Each line is given in the following format 1 Club information , One of the students from 1~N Number ：

The first i Number of clubs Mi（ Space ） Student 1（ Space ） Student 2 … Student Mi

Output format :
The output gives an integer , How many people are in the biggest circle of friends .

sample input :

7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

sample output :

4

Big guy's code ：

#include<stdio.h>
int pre[30001];
int sum[30001];
int ans=0;
void init(int n)
{
    
	for(int i=1;i<=n;i++)
	{
    
	  pre[i]=i;
	  sum[i]=1;
	}
	  
}
int find(int x)
{
    
	if(pre[x]==x)return x;
    return pre[x]=find(pre[x]);// Path compression  
}
void join(int x,int y)
{
    
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	{
    
		pre[fx]=fy;
		sum[fy]+=sum[fx];
	}
}
int main()
{
    
	int n,m;
	scanf("%d %d",&n,&m);
	init(n);
	int s;
	while(m--)
    {
    
    	scanf("%d",&s);
    	int stus[s+1];
		for(int i=1;i<=s;i++)
		{
    
	     	scanf("%d",&stus[i]);	
		}
	    for(int x=1;x<=s;x++)
	    {
    
	    	for(int z=x+1;z<=s;z++)
	    	{
    
	    		join(stus[x],stus[z]);
			}
		}
	}
	int max=0;
	for(int i=1;i<=n;i++)
	{
    
		if(sum[i]>max)max=sum[i];
	}
	printf("%d",max);
	return 0;
}

This code is not long , But there are a few key functions that I didn't understand at first ：

1.init function

void init(int n)
{
    
	for(int i=1;i<=n;i++)
	{
    
	  pre[i]=i;
	  sum[i]=1;
	}
	  
}

This function will pre and sum Global array initialization of ,pre The function represents the previous node of the student with the same meaning as the subscript ,sum The function represents the nodes of the subscript and the number of nodes below the subscript .
Because of initialization , therefore sum All for their own node ,pre All nodes temporarily saved as their own subscripts .

2.find function

int find(int x)
{
    
	if(pre[x]==x)return x;
    return pre[x]=find(pre[x]);// Path compression  
}

The function is to find friends x The head node of , Through this function, you can step by step pre The value inside becomes the subscript of the highest node corresponding to the subscript （ Path compression ）

3.join function

void join(int x,int y)
{
    
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	{
    
		pre[fx]=fy;
		sum[fy]+=sum[fx];
	}
}

This function is used to judge whether two friends are in the same circle , If so, there is no need to change , If not , Turn a friend's node into the last node of your highest node , also sum Add one

Let's get familiar with the problem-solving method

4-3-2 Union checking set tribe (25 branch )
In a community , Everyone has their own small circle , It may also belong to many different circles of friends at the same time . We think that friends of friends are all included in a tribe , So I want you to count , In a given community , How many different tribes are there ？ And check if any two people belong to the same tribe .

Input format ：
Enter a positive integer on the first line N（≤10
​4
​​ ）, Is the number of known small circles . And then N That's ok , Each line gives a small circle of people in the following format ：

K P[1] P[2] ⋯ P[K]

among K It's the number of people in a small circle ,P[i]（i=1,⋯,K） It's the number of everyone in the small circle . The number of everyone here is from 1 Start consecutive numbering , The maximum number will not exceed 10
​4
​​ .

The next line gives a nonnegative integer Q（≤10
​4
​​ ）, Is the number of queries . And then Q That's ok , Each line gives the number of a pair of people being queried .

Output format ：
First, output the total number of people in this community in one line 、 And the number of tribes that don't intersect each other . Then for each query , If they belong to the same tribe , Output in one line Y, Otherwise output N.

sample input ：

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

sample output ：

10 2
Y
N

Code ：

#include<stdio.h>
#define N 10001
int pre[N];
int sum[N];

// Function function //
void inis();
void join(int x, int y);
int find(int x);


// The main function //
int main()
{
    
    int n;
    inis();
    scanf("%d", &n);
    int people = 0;
    int m;
    int i = 0, j = 1;
    for (i = 0; i < n; i++) {
    
        scanf("%d", &m);
        int zb[100];
        for (j = 1; j <= m; j++) {
    
            scanf("%d", &zb[j]);
            if (zb[j] > people) {
    
                people = zb[j];
            }
        }
        int x;
        for (j = 1; j <= m; j++) {
    
            for (x = j + 1; x <= m; x++) {
    
                join(zb[j], zb[x]);
            }
        }
    }
    int d = 0;
    for (i = 1; i <= people; i++) {
    
        if (pre[i] == i) {
    
            d++;
        }
    }
    printf("%d %d\n", people, d);
    int aim1, aim2;
    int nm;
    scanf("%d", &nm);
    for (i = 0; i < nm; i++) {
    
        scanf("%d %d", &aim1, &aim2);
        int fx = find(aim1);
        int fy = find(aim2);
        if (fx != fy) {
    
            printf("N\n");
        }
        else {
    
            printf("Y\n");
        }
    }
}

void inis() {
    
    for (int i = 1; i <= N; i++) {
    
        pre[i] = i;
        sum[i] = 1;
    }
}
int find(int x)
{
    
    if (pre[x] == x)return x;
    return pre[x] = find(pre[x]); 
}
void join(int x, int y)
{
    
    int fx = find(x);
    int fy = find(y);
    if (fx != fy)
    {
    
        pre[fx] = fy;
        sum[fy] += sum[fx];
    }
}