Leetcode22 summary of types of questions brushing in 2002 (XII) and collection search

The template of parallel search is as follows ：

int n = 1005; //  Number of nodes 3  To  1000
int father[1005];

//  And search set initialization 
void init() {
    
    for (int i = 0; i < n; ++i) {
    
        father[i] = i;
    }
}
//  And look up the process of root searching in the collection 
int find(int u) {
    
    return u == father[u] ? u : father[u] = find(father[u]);
}
//  take v->u  This edge joins and searches the set 
void join(int u, int v) {
    
    u = find(u);
    v = find(v);
    if (u == v) return ;
    father[v] = u; // The general principle of keeping to the left , That is, let the left become the right father （, In principle, it can be left or right , Because the questions usually only ask who and who , Or a few groups , Who is the team leader , Unless the topic specifically requires ）
}
//  Judge  u  and  v Whether to find the same root 
bool same(int u, int v) {
    
    u = find(u);
    v = find(v);
    return u == v;
}

Summary of the above templates , Just modify n and father The size of the array is OK .

There are three main functions of parallel search .

1. Find the root node , function ：find(int u), That is, determine which ancestor node of this node is
2. Connect two nodes to the same set , function ：join(int u, int v), Connect two nodes to the same root node
3. Judge whether two nodes are in the same set , function ：same(int u, int v), To judge whether two nodes are the same root node

Template source ： Random code recording

Patients with a ： Catch the thief, catch the king first

Altogether 10 A robber , Number 1-10, It is known that ： Associates have ：
【1,2】、【3,4】、【5,2】、【4,6】、【2,6】、【8,7】、【9,7】、【1,6】、【2,4】
The robber's accomplice is also an accomplice , seek ： Find out how many independent criminal groups there are

#include<stdio.h>
int f[1000]={
    0},n,m,k,sum=0;
//int total=100000;
void init(){
    
    int i;
    for(i=1;i<=n;i++){
    
        f[i]=i;
    }
    return;
}

int getf(int v){
    
    if(f[v]==v)
        return v;
    else{
    
        f[v]=getf(f[v]);
        return f[v]
        // Here is path compression , Every time the function returns , Stop by to meet people on the way boss Change to the ancestral number finally found 
        // This will increase the speed of finding the ultimate ancestor 
    }
}
void merge(int v,int u){
    
    int t1,t2;//t1,t2 , respectively, int v,int u The big boss, Every time the two sides meet, they are the top leaders 
    t1=getf(v);
    t2=getf(u);
    if(t1!=t2){
    // Determine whether the two nodes are the same set 
        f[t2]=t1;//“ Keep to the left ”  principle , The left becomes the right boss
        // After path compression , hold 
        
    }
    
}

int main(){
    
    int i,x,y;
    scanf("%d",&n); //n personal 
    scanf("%d",&m);//

    init(); // initialization 
    for(i=1;i<=m;i++){
     // Data entry 
        scanf("%d %d",&x,&y);
        merge(x,y) // Merge 
        }
    
    for(i=1;i<=n;i++){
     // Find each large boss
        if(f[i]==i){
    
            sum++;
        }
    }
    printf("%d\n",sum);// How many independent criminal gangs are there in the end 
    getchar();getchar();
    return 0

    
}

Example 2 ： Circle of friends

Example 1
Input
2
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
Output
4
2

#include<bits/stdc++.h>
using namespace std;
 
unordered_map<int, int>fa;
unordered_map<int, int>cnt;
 
int find(int x){
    
    if(fa.find(x)==fa.end()){
    
        fa[x]=x;
        cnt[x]=0;
    }
    if(x==fa[x]){
    
        return x;
    }
    return fa[x]=find(fa[x]);
}
void Union(int x,int y){
    
    int fx=find(x);
    int fy=find(y);
    fa[fx]=fy;
}
int main(){
    
    int T;cin>>T;
    while(T-- >0){
    
        int n;cin>>n;
        while(n-- >0){
    
            int x,y;
            cin>>x>>y;
            Union(x,y);
        }
        int ans=0;
        for(unordered_map<int, int>::iterator it=fa.begin();it!=fa.end();it++){
    
            int fi=find(it->second);
            cnt[fi]++;
            ans=max(ans,cnt[fi]);
        }
        cout<<ans<<endl;
        fa.clear();
        cnt.clear();
    }
}

Example 3 ：684. Redundant connections

A tree can be regarded as a connected and acyclic Of Undirected chart .

Given to a tree n Nodes ( Node values 1～n) The graph after adding an edge to the tree . The two vertices of the added edge are contained in 1 To n middle , And this additional edge does not belong to the existing edge in the tree . The information of the figure is recorded in a length of n Two dimensional array of edges ,edges[i] = [ai, bi] Show in the figure ai and bi There is an edge between .

Please find an edge that can be deleted , After deletion, the remaining part can be a with n Tree of nodes . If there are multiple answers , Returns an array edges Last edge in .

class Solution {
    
private:
    int n=1005;
    int father[1005];
    void init(){
    
        for(int i=0;i<n;i++){
    
            father[i]=i;
        }
    }
    int find(int u){
    
        if(father[u]==u){
    
            return u;
        }
        return father[u]=find(father[u]);
    }
    void join(int u,int v){
    
        u=find(u);
        v=find(v);
        if(u==v) return;
        father[v]=u;
    }
    bool same(int u,int v){
    
        u=find(u);
        v=find(v);
        return u==v;
    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    
        //  The idea is to traverse each edge from front to back , If two nodes of an edge are not in the same set , Just join the collection （ namely ： The same root node ）.
        // If two nodes of an edge already appear in the same set , It indicates that the two nodes of the edge have been connected , If you add this edge again, there must be a ring .
        init();
        vector<int> ans;
        for(int i=0;i<edges.size();i++){
    
            if(same(edges[i][0],edges[i][1])){
    
                ans=edges[i];
                break;
            }
            join(edges[i][0],edges[i][1]);
        }
        return ans;
    }
};