This is the fourth day of my participation in Gwen Challenge

The introduction

Omnipresent religion

There are so many religions in the world. Suppose you are interested in how many religions your classmates have in total. We know there are n students in the school, but it is not polite to ask people about their religious beliefs directly. Another way is to ask m and his classmates whether they believe in the same religion. Based on this information, how would you be smart enough to figure out the maximum number of religious faiths at your school?

An overview of the

==Union-Find Set==

A == tree data structure == is used for merging and querying some Disjoint Sets

In use, it is usually represented by forest

Initialize: set the numbers to 1… N elements of N are divided into N disjoint sets, and in each set, one element is selected to represent the set (usually represented by the root node).

Common operations:

•**== Merges ==** two sets

•**== Finds ==** which collection an element belongs to

• Determine whether two elements belong to the same set

Basic operation

To determine whether two elements belong to the same set, you just need to determine whether the root of the set is the same

Merge two sets, using the root of one set as the root of the other

The basic function

Make_set (x) : Initializes each element as a set

Find_set (x) : Finds the collection of an element. When you perform a search, you follow the parent until you find the root

Union_set (x, y) : use find_set() to find the root of two sets and point the root of one set to the root of the other set

Heuristic strategy optimization

According to the rank merger

• Rank: The height of the tree where only one root node has Rank 0

•==union_set(x,y) merges by rank ==, == Merges relatively small rank trees into relatively large rank trees, so that the height of the merged tree will be relatively small ==

Path to the compression

• Path compression when find_set(x), after the root node is found by “recursion”, the parent of all nodes on the path points directly to the root node when “backtracking”, and the time complexity is O(1) when find_set(x) is called again.

#include <stdio.h>

const int MAXN = 100; /* Number of nodes */
int pa[MAXN];    /*pa[x] indicates the parent of x */
int rank[MAXN];    /*rank[x] is an upper bound on the height of x */

/* Create a cell set */
void make_set(int x)
{
    pa[x] = x;// it is its own parent node,
    rank[x] = 0;// The initial node has its own node with rank 0
}

/* Lookup with path compression */
int find_set(int x)
{
    if(x ! = pa[x])// My parent is not my own, so I continue to search until I find my own father
        pa[x] = find_set(p[x]); // Trace the parent of all nodes back to the root
    return pa[x];
}
/* Merge the set of x and y by rank */
void union_set(int x, int y)
{
    x = find_set(x); // Return the root of x
    y = find_set(y); // return the root of y
    if(rank[x] > rank[y])/* set the parent of a higher rank */
        pa[y] = x;// The rank of x, where x is the father and y is the son of X
    else 
    {
        pa[x] = y;// Otherwise, x's father is Y
        
        // The rank of y is the same. It doesn't matter who the father is, but if y is the father first, the rank of y will increase by 1
        if(rank[x] == rank[y]) rank[y]++; }}Copy the code

Example: PTA circle of Friends (25 points)

Circle of Friends (25 points) A school has N students, forming M clubs. Students in each club have certain similar interests, forming a circle of friends. A student can belong to several different clubs at once. If A and B are friends, and B and C are friends, then A and C are friends, too. Please write a program to calculate the number of people in the largest circle of friends.

Input format: The first line contains two positive integers N (≤30000) and M (≤1000), representing the total number of students and the number of clubs respectively. The following M lines give the information of one club in the following format, where students are numbered from 1 to N:

Number of people in club I Mi (blank) Student 1 (blank) Student 2… Students in the Mi

Output format: The output gives an integer representing the number of people in the largest circle of friends.

Example Input:

1. 3Copy the code

Example output:

4
Copy the code

After all nodes are merged, the parent nodes of all nodes are traversed, and the number of fathers of the parent node is recorded, and the number of fathers of the parent node is compared to whether it is the father with the most sons. The largest number of sons is recorded and output.

In the code

#include "bits/stdc++.h"
using namespace std;
const int maxx = 30005;
int father[maxx];
int ran[maxx];
int isRoot[maxx];

void make_set(int x)
{
    father[x] = x;
    ran[x] = 0;
}
int find(int x)
{ // Find the compression path
    if (father[x] == x)
    { // If its parent is itself, then x is the root
        return x;
    }
    return find(father[x]); // Return the root of the parent
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (ran[x] > ran[y])
    {
        father[y] = x;
    }
    else
    {
        father[x] = y;
        if(ran[x] == ran[y]) { ran[y]++; }}}int main(a)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= n; i++)
    {
        make_set(i);
    }
    int x, y;
    int k;
    int s = 1;

    for (int i = 0; i < m; i++)
    {
        cin >> k >> x;
        for (int j = 0; j < k - 1; j++)
        {
            cin >> y;
            merge(x, y); }}int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int f = find(i);
        isRoot[f]++;
        ans = max(ans, isRoot[f]);
    }
    cout << ans << endl;
}
Copy the code