【Weekly Algorithm】算法周记之《代码随想录》图论（三）
学习小结
本周跟随《代码随想录》继续学习关于图论的知识，主要是关于并查集以及最小生成树的两个经典算法（prim和kruskal）。
并查集的作用在于快速区分不同的类别并补充内容。prim 则是从点的角度从图中划分出最小生成树，kruskal 是划分边来种最小生成树。
图论
有向图的完全可达性
问题：给一个有向图，但求中的1节点是否能到达其他节点。
方法：从 1 开始 dfs/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#include <iostream>
#include <vector>
#include <list>
using namespace std;
void dfs(const vector<list<int>> grid, vector<bool> &visited, int &count, int node) {
count++;
visited[node] = true;
// 遍历每个节点所链接的部分
for (const auto &i : grid[node]) {
if (visited[i]) continue;
dfs(grid, visited, count, i);
}
}
int main() {
int n, k;
cin >> n >> k;
vector<list<int>> grid(n+1);
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
grid[a].push_back(b);
}
vector<bool> visited(n+1, false);
int count = 0;
dfs(grid, visited, count, 1);
int result;
if (count == n) {
result = 1;
}
else {
result = -1;
}
cout << result << endl;
// 测试输出图
// for (int i = 0; i < n+1; i++) {
// cout << i << ": ";
// for (auto &j : grid[i]) {
// cout << j << " ";
// }
// cout << endl;
// }
return 0;
}岛屿的周长
题意：二维数组中的岛屿没有内部水，求该一个岛屿的边缘周长。
方法：两个思路，一个是遍历岛屿，求每块的边界；第二个思路是求岛屿块数，4*块数 - 相邻区块的重叠边，该思路只要注意求相邻区块的方向不要重合，比如每个区块都只检查左上两个方向。
参考代码随想录思路的解法
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#include <iostream>
#include <vector>
using namespace std;
// 一格的四个方向
int dr[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
// 遍历统计边
int edge_num = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0) continue;
for (int k = 0; k < 4; k++) {
int nx = i + dr[k][0];
int ny = j + dr[k][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == 0) {
edge_num++;
}
}
}
}
cout << edge_num << endl;
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#include <iostream>
#include <vector>
using namespace std;
int find(vector<int> &father, int a) {
return father[a] == a ? a : father[a] = find(father, father[a]);// 路径压缩
}
int main() {
int n, m;
cin >> n >> m;
// n个点 m条边
vector<int> father(n+1, -1);
// 初始化并查集
for (int i = 0; i < n+1; i++) {
father[i] = i;
}
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a = find(father, a);
b = find(father, b);
//cout << a << " " << b << endl;
if (a != b) father[a] = b;
}
// for (int i = 0; i < n+1; i++) {
// cout << father[i] << endl;
// }
int source, destination;
cin >> source >> destination;
// 本质上就是两个点是否属于统一个并查集（同一个无向连通图）
cout << int(find(father, father[source])==find(father, father[destination])) << endl;
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#include <iostream>
#include <vector>
using namespace std;
int find(vector<int> &father, int a){ // 查找并查集所属类
return father[a] == a ? a : father[a] = find(father, father[a]);
}
bool join(vector<int> &father, int a, int b) { // 尝试合并两个点
a = find(father, a);
b = find(father, b);
if (a == b) return false;
father[a] = b;
return true;
}
int main() {
int n;
cin >> n;
vector<int> father(n, 0); // 并查集
for (int i = 0; i < n; i++) { // 初始化
father[i] = i;
}
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
if (!join(father, a, b)) {
cout << a << " " << b << endl;
break;
}
}
return 0;
}冗余连接II
题意：[[冗余连接]]的有向图版。
方法，由于无向图变成有向图，就不能无脑找那个并查集重复的那条边，这只能避免成环的情况，无法避免一个点有两个父节点的情况。
参考代码随想录思路的解法：
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#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> father(1001, 0);
// 并查集初始化
void init() {
for (int i = 1; i <= n; i++) father[i] = i;
}
// 寻根
int find(int u) {
return father[u]==u ? u : father[u] = find(father[u]);
}
// 查看是否相同
bool isSame(int p, int q) {
return find(p) == find(q);
}
// 加入并查集
void join(int p, int q) {
p = find(p);
q = find(q);
if (p == q) return;
father[p] = q;
}
// 在图里找到要删除的边
// 原理是从前向后找到第一组同一个并查集的的一组点就行
void deleteCircleEdge(const vector<vector<int>>& edges) {
init();
for (int i = 0; i < n; i++) {
if (isSame(edges[i][0], edges[i][1])) {
cout << edges[i][0] << " " << edges[i][1] << endl;
return;
}
else {
join(edges[i][0], edges[i][1]);
}
}
}
// 判断去除边后剩下能否成树
bool isDelOk(const vector<vector<int>> edges, int del) {
init();
for (int i = 0; i < n; i++) {
if (i == del) continue;
if (isSame(edges[i][0], edges[i][1])){ // 出现环说明删除到错的边了，换另一条即可
return false;
}
join(edges[i][0], edges[i][1]);
}
return true;
}
int main() {
cin >> n;
vector<vector<int>> edges; // 边的记录
vector<int> inDegree(n+1, 0); // 入度
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
edges.push_back({a,b});
inDegree[b]++;
}
// 倒序添加入度为2的点对应的边
vector<int> vec;
for (int i = n-1; i >= 0; i--) {
if (inDegree[edges[i][1]] == 2) {
vec.push_back(i);
}
}
// 处理非成环的情况
if (vec.size() > 0) {
// 只有两种情况，倒数第一条或者倒数第二条
// 因为有可能倒数第一条取出后，会产生孤立点，所以去除另一条边
if (isDelOk(edges, vec[0])) {
cout << edges[vec[0]][0] << " " << edges[vec[0]][1] << endl;
}
else {
cout << edges[vec[1]][0] << " " << edges[vec[1]][1] << endl;
}
return 0;
}
// 处理有向环
deleteCircleEdge(edges);
return 0;
}最小生成树之prim
题意：本质就是求最小生成树的值大小
方法：prim算法
分三步：- 找到与最小生成树距离最近的节点（初始化就随便一个都行）
- 把节点加入最小生成树
- 根据加入节点，更新其他节点与最小生成树的距离
但是具体实现还有很多细节，写在了注释中。
参考代码随想录思路的解法
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#include <iostream>
#include <vector>
#include <climits>// INT_MAX
using namespace std;
int main() {
int v, e;
cin >> v >> e;
vector<vector<int>> grid(v+1, vector<int>(v+1, 0));
for (int i = 0; i < e; i++) {
int x, y, k;
cin >> x >> y >> k;
grid[x][y] = k;
grid[y][x] = k;
}
vector<int> min_dist(v+1, 10001);// 题目最大值10000
vector<bool> visited(v+1, false);
// 找到构成最小生成树的v-1条边
for (int i = 1; i < v; i++) {
int min_val = INT_MAX;
int cur = -1;// 要加入最小生成树的点
for (int j = 1; j <= v; j++) { // 遍历所有点
// 找一个不在树里面，且与最小生成树距离最小的点
if (!visited[j] && min_dist[j] < min_val) {
min_val = min_dist[j];
cur = j;
}
}
// 加入最小生成树的点
visited[cur] = true;
// 遍历与加入点相连的其它点，更新与最小生成树的距离
for (int i = 1; i <= v; i++) {
if (visited[i]) continue; // 已在树内
if (grid[cur][i] == 0) continue; // 无连接
if (grid[cur][i] < min_dist[i]) {
min_dist[i] = grid[cur][i];
}
}
}
int result = 0;
for (int i = 2; i <= v; i++) { // 之所以i从2开始，是因为min_dist[1]不会赋值
// 从理解的角度，1一开始就在树内，所以没有计算距离（或是距离为0）
result += min_dist[i];
}
cout << result << endl;
return 0;
}最小生成树之kruskal
题目：与[[最小生成树之prim]]一样，但方法不同。
方法：kruskal看边，而prim看点。简单地说，kruskal会升序遍历边，不断加入不同并查集的边，最后得到最小生成树。
参考代码随想录思路的解法
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#include <iostream>
#include <vector>
#include <climits>// INT_MAX
#include <algorithm>
using namespace std;
typedef struct _Edge {
int l;
int r;
int val;
}Edge;
int n = 10001;
vector<int> father(n, 0);
int find(int u) {
return father[u]==u ? u : father[u] = find(father[u]);
}
void join(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
father[u] = v;
}
bool isSame(int u, int v) {
return find(u) == find(v);
}
void init() {
for (int i = 0; i < 10001; i++) {
father[i] = i;
}
}
int main() {
int v, e;
cin >> v >> e;
vector<Edge> edge;
while(e--) {
int l, r, val;
cin >> l >> r >> val;
edge.push_back({l, r, val});
}
sort(edge.begin(), edge.end(), [](Edge &e1, Edge &e2) {return e1.val < e2.val;});
init();
int result = 0;
for (const auto & line : edge) {
int l = find(line.l);
int r = find(line.r);
if (l != r) {
join(l, r);
result += line.val;
}
}
cout << result << endl;
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！
相关推荐
2024-11-17
【Weekly Algorithm】算法周记之《代码随想录》动态规划（一）
学习小结本周跟随《代码随想录》开始学习动态规划的相关题目，从基础的斐波那契数到爬楼梯，再到 01 背包问题，慢慢熟悉动态规划的五步法。《代码随想录》还提醒，调试重点是检查递推公式是否举例，检查打印 dp 数组是否和自己设想一致。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 此外除了寻常的二维数组动态规划，也尝试做滚动数组的练习。 动态规划 斐波那契数 题意，给一个数字 n，求斐波那契数中的第 n 个数 方法，虽然就算不看代码随想录也能轻易写出，但简单题的重点在于熟悉套路方法，下面按五步分析 确定 dp 数组及其下标含义，这里的 dp[i] 代表斐波那契数中的第 i 个数 确认递推公式，题目给出 dp[i]=dp[i-1]+dp[i-2] dp 数组初始化，题目也给出dp[0]=0;dp[1]=1; 确定遍历顺序，从递推公式可见，就是从前向后（0-n）遍历 举例推导 dp 公式，0 1 1 2 3 5 8 13 21 …… 陆爻齐的解 1234567891011121314class...
2024-11-24
【Weekly Algorithm】算法周记之《代码随想录》动态规划（二）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，由于期末月的到来，以及题目难度的增加，暂且将动态规划的学习进度放慢一点。下面继续巩固五步法。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 只能感叹，这动态规划真是一百道题才入门啊。 动态规划 分割等和子集 代码随想录 416. 分割等和子集 - 力扣（LeetCode） 题意，给一个数组，返回判断该数组是否能平分为和相等的两部分 方法，直觉上，可以用回溯遍历树，找到那个子节点，但复杂度太高。本题其实就是 01 背包的应用，nums[i] 本身，是物品，重量，以及价值。数组能否平分和的本质，就是平分和的大小的背包能否被刚好装满，也就是下标与值相等。 参考代码随想录思路的代码 1234567891011121314151617class Solution {public: bool canPartition(vector<int>& nums) { int sum =...
2024-12-01
【Weekly Algorithm】算法周记之《代码随想录》动态规划（三）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，主要是完全背包的入门，体会其与 01 背包的不同与关联。 下周两门考试，教务脑子真是进了水，搞这么紧干嘛。 动态规划 完全背包理论 代码随想录 52. 携带研究材料（第七期模拟笔试） 题目，与 [[01背包理论]]的差别在于一个物品可携带多次，求最大价值 方法， dp[j]，在遍历物品时，截止到空间为 j，可装入的最大价值 递推公式，dp[j]=max(dp[j],dp[j-weigh[i]]+val[i]) 初始化，全 0 遍历方向，重点，这是与 01 背包区别最大的地方，01 的滚动数组强调倒序遍历就是为了避免重复，在完全背包中，恰恰需要正序从而利用重复装入物品 举例，…… 参考代码随想录思路的解法 12345678910111213141516171819202122232425262728#include <iostream>#include <vector>using namespace std;int main() { int n, v; ...
2024-12-15
【Weekly Algorithm】算法周记之《代码随想录》动态规划（五）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学会了完全背包的应用，多重背包的理论，打劫打家劫舍问题，和股票买卖问题的入门版。认识到了所存储的状态并不只有 整数 这一种形式，还能有多个整数并成的 vector 作为状态使用。 不得不说，动态规划十分的灵活，一百道题入门还不是说说而已啊。 动态规划 完全平方数 代码随想录 279. 完全平方数 - 力扣（LeetCode） 题意，给一个整数 n，求其被完全平方数组成的最小个数。 方法，就是[[零钱兑换II]]的变体，给的零钱变成了自己找小于 n 的完全平方数，背包容量为 n dp[j] 含义为 在背包容量为 j 的情况下，完全平方数的最小组合 递推公式，dp[i]=min(dp[i],dp[i-j*j]+1)，也就是要么保持不变，要么就在已有的组合上加一 初始化，dp[0]=0,这是为了递推公式才这么初始化，也能理解，完全平方数不算...
2025-01-12
【Weekly Algorithm】算法周记之《代码随想录》动态规划（六）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习完买卖股票相关内容，并初步探索子序列的部分。 买卖股票的题有明显的状态转换，但子序列就没那么明显。 动态规划 买卖股票的最佳时机II 代码随想录 122. 买卖股票的最佳时机 II - 力扣（LeetCode） 题意，在[[买卖股票的最佳时机]]的基础上，要求可以多次购买股票，但同一时段只能持有一支股票，也就是再卖出上一支股票前，不允许购入下一支股票。 方法，与[[买卖股票的最佳时机]]的差别，在于考虑购入当前股票时，是在上一支股票考虑购入和卖出的两个情况中取最大，并非直接取历史最便宜股票和当前股票对比。 参考代码随想录思路解法 123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { // dp[i][0] 考虑第i支股票时，考虑买入的情况；dp[i][1] 考虑第i支股票时，卖出的情况 int len =...
2025-02-09
【Weekly Algorithm】算法周记之《代码随想录》单调栈和图论（一）
学习小结本周跟随《代码随想录》学习关于单调栈的知识，同时开启图论。 单调栈通过保持一个栈从栈顶到栈底的递增或是递减序列，来解决找一个元素左/右的“第一个”更大/更小元素。 图论则是初窥dfs的门路，虽然道理一年前早在算法课学过考过，但现在也得复习才能捡回来。 单调栈 每日温度 代码随想录 739. 每日温度 - 力扣（LeetCode） 题意：给一个整数数组，求每个数字右侧比该数字更大的间距 方法：暴力解法就是O(n^2)的遍历。更高效率的方法是使用单调栈，所谓的单调栈就是从栈顶到栈底递增或递减的，如此排列，就能方便找任意元素的左右第一个更大更小的元素。 比如本题是找右边更大的，那么遍历数组时，遇到更小或相等的元素就直接入栈，而遇到更大的元素就弹栈，直到触底或碰到大元素再入栈，其中弹栈的元素就能记录本元素的下标与当时元素下标之差。 参考代码随想录思路的解法 12345678910111213141516171819202122232425class Solution {public: vector<int>...
系列文章