当前位置：首页 > article >正文

最大连通块之DFS，BFS

article 2024/11/20 0:42:28

纯音~

🍌前言

🍌作业

🌳一，最大连通

🌼AC DFS + 剪枝

🌼AC BFS + 剪枝

🌳二，1136: 最大黑区域

🌼AC DFS + 剪枝

🌼AC BFS + 剪枝

01矩阵本来就是BFS / DFS剪枝的活，该死的并查集

本来就很难实现，还有垃圾gpt，害我以为它的思路完全正确，还是差了点东西

🍌前言

做C++作业时，遇到了求最大连通块的题，一开始以为并查集能解决，但不好实现，折腾了一个小时没结果

经搜索发现，这道题暴力dfs + 剪枝很好实现

不要以为剪枝有多么高深，本题只是一个vis[][]数组判断是否访问过而已（类似book的标记数组）

if(vis[i][j] == 0)，表示未访问过

然而，dfs其实是很灵活的，主要体现在参数设置上面，可以说是千变万化

初学dfs的人，总会刻意背模板，记参数，这样是不行的，有些dfs一个参数，有些2个，有些3个4个，这个得看需要，怎么方便怎么来

总结5个字：做题做少了

下面我将结合作业，以及洛谷，AcW，New Oj上找的求最大连通块的题，来阐述思路和代码

更重要的是，方便三五个月后的复盘，到时重新看看自己当初写的东西，重新AC一遍岂不快哉

🍌作业

就是找01方阵中的最大连通块，单靠并查集模板可不好办，因为求的是最大连通块的总数

而不是一共有多少个互不相连的集合

当然，如果只是一维元素，是可以用并查集维护元素个数的，但二维不好实现，而且没有题解靠自己摸索不好debug

思路

1，按int e[][]输入n阶方阵

2，dfs()四个参数x, y, color, cnt，表示横坐标，纵坐标，颜色(0 / 1)，计数(count)

3，遍历方阵，对每一个未被访问过的点进行dfs（因为有vis[][]数组的剪枝，不会超时）

4，dfs过程记录连通块大小，并在每个点遍历的结尾用ans保存cnt最大值

额外的测试

代码1 O(nm) == O(n^2)

小BUG

void dfs()参数里有个int &cnt，但是我不熟悉&，所以不建议用，因为一开始

递归那里，我直接dfs(tx, ty, color, cnt + 1);

于是报错error: reference to 'next' is ambigious，因为next可能是关键字或者重载

类似max, min, next这种不确定会不会报错的尽量不要用

另一种方式

当然还有个点，代码第16~20行，可以不需要nex[][]方向数组，当然做Bfs一般还是需要方向数组的

可以直接4个递归，效果是一样的（详情看代码2）

#include<iostream>
using namespace std;
int n, ans, cnt;
int e[110][110], vis[110][110]; //e保存地图, vis标记访问
int nex[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组
void dfs(int x, int y, int color, int &cnt)
{
    if(x < 0 || y < 0 || x >= n || y >= n)
        return; //越界
    if(e[x][y] != color || vis[x][y] == 1)
        return; //颜色不同或访问过
    vis[x][y] = 1; //标记
    cnt += 1;
    int tx, ty;
    //遍历四个方向
    for(int i = 0; i < 4; ++i) {
        tx = x + nex[i][0];
        ty = y + nex[i][1];
        dfs(tx, ty, color, cnt);
        //本题不需要取消标记
    }
}
int main()
{
    cin>>n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin>>e[i][j];
    //暴力dfs + 剪枝, 剪枝通过标记数组实现
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j) {
            cnt = 0; //每个未访问过的点重新计算连通块数
            if(vis[i][j] == 0) { //未访问过
                dfs(i, j, e[i][j], cnt);
            }
            ans = max(ans, cnt);
        }
    cout<<ans;
    return 0;
}

代码2

直接去掉cnt参数，在全局cnt操作；同时，采用4行递归来代替方向数组。

#include<iostream>
using namespace std;
int n, ans, cnt;
int e[110][110], vis[110][110]; //e保存地图, vis标记访问
void dfs(int x, int y, int color)
{
    if(x < 0 || y < 0 || x >= n || y >= n)
        return; //越界
    if(e[x][y] != color || vis[x][y] == 1)
        return; //颜色不同或访问过
    vis[x][y] = 1; //标记
    cnt += 1;
    //遍历四个方向
    dfs(x + 1, y, color);
    dfs(x - 1, y, color);
    dfs(x, y + 1, color);
    dfs(x, y - 1, color);
}
int main()
{
    cin>>n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin>>e[i][j];
    //暴力dfs + 剪枝, 剪枝通过标记数组实现
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j) {
            cnt = 0; //每个未访问过的点重新计算连通块数
            if(vis[i][j] == 0) { //未访问过
                dfs(i, j, e[i][j]);
            }
            ans = max(ans, cnt);
        }
    cout<<ans;
    return 0;
}

🌳一，最大连通

最大连通 - 蓝桥云课 (lanqiao.cn)

2023第14届蓝桥杯第3次模拟赛填空第5题

注意不要将原代码直接在官网上提交

1，官网编译很垃圾 2，直接cout保险很多

作业代码的基础上

1，去掉输入的n，改为30行60列的矩阵了（不是方阵）

2，同时int e[][]改为char e[][]

3，color参数都不用了，因为只用考虑1，当然你不去掉也能输出148，因为1比0的最大更大

🌼AC DFS + 剪枝

本地编译器代码 O(nm) == O(1)

#include<iostream>
using namespace std;
int ans, cnt;
int vis[110][110]; //vis标记访问
char e[110][110]; //e保存地图
void dfs(int x, int y)
{
    if(x < 0 || y < 0 || x >= 30 || y >= 60)
        return; //越界
    if(e[x][y] != '1' || vis[x][y] == 1)
        return; //颜色不同或访问过
    vis[x][y] = 1; //标记
    cnt += 1;
    //遍历四个方向
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
}
int main()
{
    for(int i = 0; i < 30; ++i)
        for(int j = 0; j < 60; ++j)
            cin>>e[i][j];
    //暴力dfs + 剪枝, 剪枝通过标记数组实现
    for(int i = 0; i < 30; ++i)
        for(int j = 0; j < 60; ++j) {
            cnt = 0; //每个未访问过的点重新计算连通块数
            if(vis[i][j] == 0) { //未访问过
                dfs(i, j);
            }
            ans = max(ans, cnt);
        }
    cout<<ans;
    return 0;
}

输入输出


110010000011111110101001001001101010111011011011101001111110

010000000001010001101100000010010110001111100010101100011110

001011101000100011111111111010000010010101010111001000010100

101100001101011101101011011001000110111111010000000110110000

010101100100010000111000100111100110001110111101010011001011

010011011010011110111101111001001001010111110001101000100011

101001011000110100001101011000000110110110100100110111101011

101111000000101000111001100010110000100110001001000101011001

001110111010001011110000001111100001010101001110011010101110

001010101000110001011111001010111111100110000011011111101010

011111100011001110100101001011110011000101011000100111001011

011010001101011110011011111010111110010100101000110111010110

001110000111100100101110001011101010001100010111110111011011

111100001000001100010110101100111001001111100100110000001101

001110010000000111011110000011000010101000111000000110101101

100100011101011111001101001010011111110010111101000010000111

110010100110101100001101111101010011000110101100000110001010

110101101100001110000100010001001010100010110100100001000011

100100000100001101010101001101000101101000000101111110001010

101101011010101000111110110000110100000010011111111100110010

101111000100000100011000010001011111001010010001010110001010

001010001110101010000100010011101001010101101101010111100101

001111110000101100010111111100000100101010000001011101100001

101011110010000010010110000100001010011111100011011000110010

011110010100011101100101111101000001011100001011010001110011

000101000101000010010010110111000010101111001101100110011100

100011100110011111000110011001111100001110110111001001000111

111011000110001000110111011001011110010010010110101000011111

011110011110110110011011001011010000100100101010110000010011

010011110011100101010101111010001001001111101111101110011101
148

AC 代码

#include <iostream>
using namespace std;
int main()
{
  cout<<148;
  return 0;
}

🌼AC BFS + 剪枝

一个月不碰BFS又忘光了，代码第20，21行，应该是q[head].x和q[head].y的

第一次回顾bfs敲成xx, yy了，难怪一直输出3，找了半小时才找到原因。。

#include<iostream>
using namespace std;
char e[110][110];
int vis[110][110], cnt, ans, head, tail, tx, ty;
int nex[4][2] = {{1,0},{-1,0},{0,-1},{0,1}}; //方向数组
struct node
{
    int x, y;
}q[2000];
void bfs(int xx, int yy)
{
    vis[xx][yy] = 1; //标记
    //往队列插入遍历起点(xx, yy)
    q[tail].x = xx;
    q[tail].y = yy;
    tail++;
    while(head < tail) {
        //枚举4个方向
        for(int i = 0; i < 4; ++i) {
            tx = q[head].x + nex[i][0]; //这里是q[head].x
            ty = q[head].y + nex[i][1]; //q[head].y
            //判断越界
            if(tx < 0 || ty < 0 || tx >= 30 || ty >= 60)
                continue;
            //是1且未访问过
            if(e[tx][ty] == '1' && vis[tx][ty] == 0) {
                vis[tx][ty] = 1; //标记
                //每个点只入队一次, 不需要取消标记
                //新的点入队
                q[tail].x = tx;
                q[tail].y = ty;
                cnt++; //新的点入队意味着连通块更大了
                tail++;
            }
        }
        head++; //继续后续点扩展
    }
}
int main()
{
    for(int i = 0; i < 30; ++i)
        for(int j = 0; j < 60; ++j)
            cin>>e[i][j];
    //暴力bfs + 剪枝
    for(int i = 0; i < 30; ++i)
        for(int j = 0; j < 60; ++j) {
            //未被访问过且是1
            if(vis[i][j] == 0 && e[i][j] == '1') {
                vis[i][j] = 1; //这个别忘！！！
                cnt = 1; //第一个点
                bfs(i, j);
            }
            ans = max(ans, cnt);
        }
    cout<<ans;
    return 0;
}

🌳二，1136: 最大黑区域

P1136 - 最大黑区域 - New Online Judge (ecustacm.cn)

标签：深度优先搜索，基础题

和上面基本一样，出现的变化有

1，初始化问题

多次输入输出，所以像ans, vis[][]数组的初始化要注意，e[][]因为还会输入的关系不用多次初始化

而cnt是在第二层for循环里初始化

第一次代码第23和25行忘记初始化，导致一直AC 50%，OI赛制可没有反馈，这只能靠经验了

2，color参数也不需要了

只能说，蓝桥杯模拟赛和这道题，都是作业题的简化版本，少了个color参数，只需要对一个颜色分析

🌼AC DFS + 剪枝

#include<iostream>
#include<cstring> //memset()
using namespace std;
int n, m, ans, cnt;
int e[110][110], vis[110][110]; //vis标记访问, e保存地图
void dfs(int x, int y)
{
    if(x < 0 || y < 0 || x >= n || y >= m)
        return; //越界
    if(e[x][y] == 0 || vis[x][y] == 1)
        return; //元素为0或访问过
    vis[x][y] = 1; //标记
    cnt += 1;
    //遍历四个方向
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
}
int main()
{
    while(cin>>n>>m) {
        ans = 0; //初始化
        if(n == 0 && m == 0) break;
        memset(vis, 0, sizeof(vis)); //初始化
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                cin>>e[i][j];
        //暴力dfs + 剪枝, 剪枝通过标记数组实现
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j) {
                cnt = 0; //每个未访问过的点重新计算连通块数
                if(vis[i][j] == 0) { //未访问过
                    dfs(i, j);
                }
                ans = max(ans, cnt);
            }
        cout<<ans<<endl;
    }
    return 0;
}

🌼AC BFS + 剪枝

麻了，代码第43，44，45行初始化，ans, vis[][], head, tail都要初始化，

因为我是结构体数组模拟队列，初始化的更多了

#include<iostream>
#include<cstring> //memset()
using namespace std;
int e[110][110];
int vis[110][110], cnt, ans, head, tail, tx, ty, n, m;
int nex[4][2] = {{1,0},{-1,0},{0,-1},{0,1}}; //方向数组
struct node
{
    int x, y;
}q[10010];
void bfs(int xx, int yy)
{
    vis[xx][yy] = 1; //标记
    //往队列插入遍历起点(xx, yy)
    q[tail].x = xx;
    q[tail].y = yy;
    tail++;
    while(head < tail) {
        //枚举4个方向
        for(int i = 0; i < 4; ++i) {
            tx = q[head].x + nex[i][0]; //这里是q[head].x
            ty = q[head].y + nex[i][1]; //q[head].y
            //判断越界
            if(tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            //是1且未访问过
            if(e[tx][ty] == 1 && vis[tx][ty] == 0) {
                vis[tx][ty] = 1; //标记
                //每个点只入队一次, 不需要取消标记
                //新的点入队
                q[tail].x = tx;
                q[tail].y = ty;
                cnt++; //新的点入队意味着连通块更大了
                tail++;
            }
        }
        head++; //继续后续点扩展
    }
}
int main()
{
    while(cin>>n>>m) {
        ans = 0; //多次输入一定要初始化!!!
        memset(vis, 0, sizeof(vis)); //多次输入一定要初始化!!!
        head = 0, tail = 0; //多次输入一定要初始化!!!
        if(n == 0 && m == 0) break;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                cin>>e[i][j];
        //暴力bfs + 剪枝
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j) {
                //未被访问过且是1
                if(vis[i][j] == 0 && e[i][j] == 1) {
                    vis[i][j] = 1; //这个别忘！！！
                    cnt = 1; //第一个点
                    bfs(i, j);
                }
                ans = max(ans, cnt);
            }
        cout<<ans<<endl;
    }
    return 0;
}

查看全文

http://www.kler.cn/a/6938.html