图论

图论习题

dfs和bfs 的岛屿问题

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>

using namespace std;

const int N = 100;

int g[N][N],st[N][N];
int n,m,res;

int ax[4] = {1,-1,0,0};
int ay[4] = {0,0,1,-1};

void dfs(int i,int j){
    for(int t=0;t<4;t++){
        int x = i+ax[t]; int y = j+ay[t];
        if(x>=0 && x<n && y>=0 && y<m && !st[x][y] && g[x][y]){
            st[x][y] = 1; //设置访问过
            dfs(x,y);
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> g[i][j];
        }
    }
    memset(st,0,sizeof(st));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!st[i][j] && g[i][j]){
                st[i][j] = 1; //设置访问过
                res ++;
                dfs(i,j);
            }
        }
    }
    cout << res;
    return 0;
}

孤岛

思路：先把图中的靠边的岛屿变成海洋，再进行遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;

const int N = 100;

int n,m,s;
int g[N][N],st[N][N];
int ax[4] = {1,-1,0,0};
int ay[4] = {0,0,1,-1};

void dfs(int i,int j){
    st[i][j] = 1;
    for(int k=0;k<4;k++){
        int x = i + ax[k];
        int y = j + ay[k];
        if(x >=0 && x< n && y >=0 && y < m && !st[x][y] && g[x][y]){
            st[x][y] = 1;
            s ++;
            dfs(x,y);
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> g[i][j];
        }
    }
    memset(st,0,sizeof(st));
    
    //最左边和最右边
    for(int i=0;i<n;i++){
        if(g[i][0]) dfs(i,0);
        if(g[i][m-1]) dfs(i,m-1);
    }
    //最上边和最下边
    for(int j=0;j<m;j++){
        if(g[0][j]) dfs(0,j);
        if(g[n-1][j]) dfs(n-1,j);
    }
    
    int res = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!st[i][j] && g[i][j]){
                s = 1;
                dfs(i,j);
                res += s;
            }
        }
    }
    cout << res;
    return 0;
}

沉没孤岛

思路：
通过st（标志状态） 和 g（存储图） 两个数组来控制岛屿的遍历 以及 变化（改变矩阵值）

  1. 第一个 dfs 来找出那些以四条边有关的非孤岛的岛屿，通过st数组将他们标记成已遍历

  2. 第二个 dfs2 来对孤岛进行遍历并改变g数组的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>

using namespace std;

const int N = 100;

int n,m;
int g[N][N],st[N][N];
int ax[4] = {1,-1,0,0};
int ay[4] = {0,0,1,-1};

void dfs(int i,int j){
    st[i][j] = 1;
    for(int k=0;k<4;k++){
        int x = i + ax[k];
        int y = j + ay[k];
        if(x >=0 && x< n && y >=0 && y < m && !st[x][y] && g[x][y]){
            st[x][y] = 1;
            dfs(x,y);
        }
    }
}

void dfs2(int i,int j){
    st[i][j] = 1;
    g[i][j] = 0;
    for(int k=0;k<4;k++){
        int x = i + ax[k];
        int y = j + ay[k];
        if(x >=0 && x< n && y >=0 && y < m && !st[x][y] && g[x][y]){
            st[x][y] = 1;
            g[x][y] = 0;
            dfs2(x,y); //这里也要写dfs2
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> g[i][j];
        }
    }
    memset(st,0,sizeof(st));
    
    //最左边和最右边
    for(int i=0;i<n;i++){
        if(g[i][0]) dfs(i,0);
        if(g[i][m-1]) dfs(i,m-1);
    }
    //最上边和最下边
    for(int j=0;j<m;j++){
        if(g[0][j]) dfs(0,j);
        if(g[n-1][j]) dfs(n-1,j);
    }
    
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!st[i][j] && g[i][j]){
                dfs2(i,j);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout << g[i][j] << " ";
        }
        if(i == n-1) break;
        cout << "\n";
    }
    return 0;
}

建造最大岛屿

求岛屿面积注意事项：

  1. s = 1; // 这里为 1 而不是 0，起点开始从1累加
  2. 要先计算一遍面积，再用两个fou循环去改变岛屿矩阵
    防止出现如下样例答案为1，而输出为0
    暴力：外层两个for循环嵌套内部两个for循环 ： n^4
    优化：给每个岛屿进行编号（从2开始，矩阵值为1代表还未编号），然后对海水即矩阵值为0的地方开始遍历，将其周围的岛屿面积相加
    1
    2
    1 1
    1  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

using namespace std;

const int N = 200;

int n,m,s;
int g[N][N],st[N][N];

int ax[4] = {0,0,1,-1};
int ay[4] = {1,-1,0,0};

void dfs(int i,int j){
    for(int k=0;k<4;k++){
        int x = i+ax[k];
        int y = j+ay[k];
        if(x>=0 && x<n && y >=0 && y<m && !st[x][y] && g[x][y]){
            st[x][y] = 1;
            s++;
            dfs(x,y);
        }
        
    }
    
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> g[i][j];
        }
    }
    int maxs = 0;
    memset(st,0,sizeof(st));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!st[i][j] && g[i][j]){
                st[i][j] = 1;
                s = 1;
                dfs(i,j);
                maxs = max(maxs,s);
            }
        }
    }
    for(int a=0;a<n;a++){
        for(int b=0;b<m;b++){
            if(g[a][b] == 0){
                g[a][b] = 1;
                memset(st,0,sizeof(st));
                for(int i=0;i<n;i++){
                    for(int j=0;j<m;j++){
                        if(!st[i][j] && g[i][j]){
                            st[i][j] = 1;
                            s = 1;
                            dfs(i,j);
                            maxs = max(maxs,s);
                        }
                    }
                }
                g[a][b] = 0;
            }
        }
    }

    cout << maxs;
    return 0;
}

有向图的可达性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int u){
    st[u] = 1;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j]){
            dfs(j);
        }
    }
}

    dfs(1);
    bool flag = true;
    for(int i=1;i<=n;i++){
        if(!st[i]){
            flag = false;
        }
    }
    if(flag) cout << 1;
    else{
        cout << -1;
    }

岛屿的周长

思路：
遍历所有岛屿，判断其四周（上下左右四个方向）的情况，满足以下条件则周长加1

1
2
3
4
5
6
7
8
if(g[x][y] == 0
        || x < 0
        || x >= n
        || y < 0
        || y >= m
    ){
    res++;        
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n,m;
int g[N][N];
int ax[4] = {0,0,-1,1};
int ay[4] = {1,-1,0,0};

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> g[i][j];
        }
    }
    int res = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j] == 1){
                for(int k=0;k<4;k++){
                    int x = i+ax[k];
                    int y = j+ay[k];
                    if(g[x][y] == 0
                            || x < 0
                            || x >= n
                            || y < 0
                            || y >= m
                        ){
                        res++;        
                    }
                        
                }
            }
        }
    }
    cout << res;
    return 0;
}

bfs 问题：小镇购物

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e4+10;
const int M = 1e6;

int n,m,k,s;
int h[N],e[M],ne[M],idx;
int st[N];

int a[N]; //a[i] = j 代表第i个商店的商品种类为j
bool buy[110]; //第i钟商品是否购买  1≤ k ≤ min(n,100)

void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}

int bfs(int u){
    memset(st,-1,sizeof(st));
    memset(buy,0,sizeof(buy));
    
    buy[a[u]] = true; //这里应该是 a[u] 去置为true，而不是buy[u] = true;
    int cnt = 1; //起点直接就被算上
    int res = 0;
    
    queue<int> q;
    st[u] = 0;
    q.push(u); // 节点
    
    
    while(q.size()){
        int t = q.front();
        q.pop();
        
        for(int i=h[t];i!=-1;i=ne[i]){
            int j = e[i];
            if(st[j] == -1){
                // cout << j << ' ' << d[j] << endl; 
                st[j] = st[t] + 1;
                
                q.push(j);
                
                
                if(!buy[a[j]]){
                    buy[a[j]] = true;
                    cnt ++;
                    res += st[j];
                }
                
                if(cnt == s) return res;
            }
        }
    }
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    while(cin >> n >> m >> k >> s){

        memset(h,-1,sizeof(h));
        // memset(e,0,sizeof(e));
        // memset(ne,0,sizeof(ne));
        
        // memset(a,0,sizeof(a));
        
        idx = 0;
        
        for(int i=1;i<=n;i++){
            cin >> a[i];
        }
        
        for(int i=0;i<m;i++){
            int a,b;
            cin >> a >> b;
            add(a,b); add(b,a);
        }       
        
        //当只需要买一种商品时，此时所有的位置出发都不需要派遣队伍出去，即代价为0
        //注意这种判断一定要得把改组所有测试数据都接收完在进行
        if(s == 1){
            for(int i=1;i<=n;i++){
                cout << 0 << " ";
            }
        }
        else{
            for(int i=1;i<=n;i++){
                cout << bfs(i) << " ";
            }
        }
        cout << "\n";
    }

    
    return 0;
}

图论
https://cs-lb.github.io/2024/06/26/搜索与图论/图论/
作者
Liu Bo
发布于
2024年6月26日
许可协议