【蓝桥杯】考前押题–并查集

?考前冲刺?

?1、合根植物

?2、亲戚

?3、七段码


✏️记笔记:

并查集属于高级算法的一种,但是根据历年省赛真题来看,只要掌握了该模板,那几乎就是送分题哦,我将从这三道经典的并查集题目来带大家学习并查集模板!!

?1、合根植物

?问题描述

样例输入

5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

样例输出

5

 其合根情况参考下图:

package Day_Day_work;

import java.util.Scanner;

/**
 * @author yx
 * @date 2022-03-25 20:18
 */
public class 合根植物___并查集 {
    static int[] father=new int[1000010];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m=scanner.nextInt();
        int n=scanner.nextInt();
        int k=scanner.nextInt();
        for (int i = 1; i <=m*n ; i++) {//初始化父节点
            father[i]=i;
        }
        for (int i = 0; i < k; i++) {
            int a=scanner.nextInt();
            int b=scanner.nextInt();
            if(Findfather(a)!=Findfather(b)){
                union(a,b);
            }
        }
        int ans=0;
        for (int i = 1; i <=m*n ; i++) {
            if(father[i]==i){
                ans++;
            }
        }
        System.out.println(ans);
    }

    private static int Findfather(int a) {//寻找祖宗节点
        if(a==father[a]){
            return a;
        }
        /**
         * 路径压缩
         */
//        return Findfather(father[a]);
        father[a]=Findfather(father[a]);//父节点设置为根节点
        return father[a];
    }

    private static void union(int a, int b) {//合并
        a=Findfather(father[a]);
        b=Findfather(father[b]);
//        if(Findfather(a)!=Findfather(b)){
//            father[Findfather(a)]=b;
//        }
        if(a!=b){
            father[a]=b;
        }
    }
}

?题解分析:

(1)这是一道非常适合入门的并查集题目,简单易懂,模板十分清晰

(2)我来给大家分析一下模板的三要素:

1、初始化每一个父节点(即i的父节点为i自身)

2、Findfather()函数,用来寻找该节点的“祖宗”节点(一直往上寻找根节点)

3、union()函数,用来合并两个节点(将a的祖宗节点设置为b,ab就属于一个集合了)

(3)博主解释下面这行代码,当我们不断地合并节点后,每一个“子节点”的“父节点”都最终指向根节点那么我们怎么判断一共有多少个集合呢?我们不难发现一个集合中只有其根节点的父节点是指向自己的,那就好办了,当有一个节点其父节点等于自己,那么就代表有一个集合,也就是下面的这行记录集合数量的代码了

if(father[i]==i)
{  ans++;    }                  

?2、亲戚

?问题描述

输入

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

输出

Yes
Yes
No
package Day_Day_work;

import java.util.Scanner;

/**
 * @author yx
 * @date 2022-04-04 19:06
 */
public class 亲戚__并查集 {
    static int fa[]=new int[5010];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        int q=scanner.nextInt();
        for (int i = 1; i <=n ; i++) {//初始化亲戚
            fa[i]=i;
        }
        for (int i = 1; i <=m ; i++) {
            int a=scanner.nextInt();
            int b=scanner.nextInt();
            gx(a,b);
        }
        for (int i = 1; i <=q ; i++) {
            int a=scanner.nextInt();
            int b=scanner.nextInt();
            if(find(a)==find(b)){
                System.out.println("Yes");
            }
            else {
                System.out.println("No");
            }
        }
    }
    static void gx(int x,int y){//合并操作
        fa[find(x)]=find(y);
        return;
    }
    static int find(int x){//找祖先
        if(fa[x]==x){
            return x;
        }
        fa[x]=find(fa[x]);
        return fa[x];
    }
}

?题解分析:

(1)该题是来源于洛谷的一道蛮经典的并查集入门题

(2)该题官方给的答案是用按秩合并来做的,博主为了让大家更好地理解并查集模板,采用传统解法

(3)聪明的小伙伴不难发现该题代码中的:

gx()函数就是上道题目的union()函数

find函数就是上道题目的Findfather()函数

(4)套路可谓是一毛一样,即使我们不会按秩合并,用常规的并查集模板也可以给它秒了

(5)注意看find()函数中使用了一行代码进行路径压缩(父节点直接指向根节点),优化了查找的复杂度

fa[x]=find(fa[x]);

?3、七段码

?问题描述

package Day_Day_work.problem;

/**
 * @author yx
 * @date 2022-04-03 23:12
 */
public class 七段码__dfs__并查集 {
    static int e[][]=new int[8][8];//存储灯管的连通情况
    static int fa[]=new int[8];//并查集的父节点
    static boolean isTrue[]=new boolean[8];
    static int ans=0;
    public static void main(String[] args) {
        //连边建图
        //a b c d e f g
        //1 2 3 4 5 6 7
        //e[i][j]=1表示i灯光和j灯光是相互连接的
        e[1][2]=e[1][6]=1;
        e[2][1]=e[2][7]=e[2][3]=1;
        e[3][2]=e[3][4]=e[3][7]=1;
        e[4][3]=e[4][5]=1;
        e[5][4]=e[5][6]=e[5][7]=1;
        e[6][1]=e[6][5]=e[6][7]=1;
        dfs(1);
        System.out.println(ans);
    }
    static void dfs(int n){
        if(n==8){//出口,遍历了每一盏灯的情况
            for (int i = 1; i <=7 ; i++) {//初始化每一个父节点
                fa[i]=i;
            }
            for (int i = 1; i <=7 ; i++) {
                for (int j = 1; j <=7 ; j++) {
                    if(isTrue[i]&&isTrue[j]&&e[i][j]==1){//如果当前两盏相互连接的灯处于打开的状态则放在一个集合里
                        fa[find(i)]=find(j);//合并操作
                    }
                }
            }
            int cnt=0;//用来记录联通情况
            for (int i = 1; i <=7 ; i++) {
                if(isTrue[i]&&fa[i]==i){
                    cnt++;
                }
            }
            //当有且仅有一种联通亮灯情况的时候才合法,这个时候ans++
            if(cnt==1)ans++;
            return;
        }
        isTrue[n]=true;//当前第n盏灯是打开的
        dfs(n+1);//递归
        isTrue[n]=false;//当前第n盏灯是关闭的
        dfs(n+1);
    }
    static int find(int x){//寻找父节点
        if(x==fa[x]){
            return x;
        }else {
            fa[x]=find(fa[x]);
            return fa[x];
        }
    }
}

?题解分析:

(1)这个题目是一道填空题,比较综合(dfs+并查集),考察难度不输一般大题

(2)用二维数组模拟灯泡i和灯泡j的相邻情况(相邻为1)

(3)dfs枚举每一个灯的亮灭组成的所有情况(一共有2^7种可能)

(4)解释一下下面这行代码,当有且仅有一种联通亮灯情况的时候才合法,这个时候ans++

举个例子:

 a和b构成一种联通;e和d构成一种联通,cnt=2,这个时候不符合题意,直接pass

            if(cnt==1)ans++;
            return;

?写在最后 

距离蓝桥杯只有四天啦!!

博主争取再更一篇BFS的押题篇,希望大家多多支持!✨

最后,博主想送给大家一句话:

你逆光而来

配得上所有的美好

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>