代码随想录算法训练营第五十四天|Day54 图论

冗余毗连

  

https://www.programmercarl.com/kamacoder/0108.%E5%86%97%E4%BD%99%E8%BF%9E%E6%8E%A5.html

  思绪

1. #include <stdio.h>
2. #include <stdlib.h>
4. #define MAX_N 1000
6. // 并查集结构体
7. typedef struct {
8.     int parent[MAX_N + 1]; // 存储每个节点的父节点
9.     int rank[MAX_N + 1];   // 存储每个节点的秩
10. } UnionFind;
12. // 初始化并查集
13. void initUnionFind(UnionFind* uf, int n) {
14.     for (int i = 1; i <= n; i++) {
15.         uf->parent[i] = i; // 每个节点的父节点为自身
16.         uf->rank[i] = 0;    // 初始秩为0
17.     }
18. }
20. // 查找根节点
21. int find(UnionFind* uf, int x) {
22.     if (uf->parent[x] != x) {
23.         // 路径压缩
24.         uf->parent[x] = find(uf, uf->parent[x]);
25.     }
26.     return uf->parent[x];
27. }
29. // 合并两个集合
30. int unionSets(UnionFind* uf, int x, int y) {
31.     int rootX = find(uf, x);
32.     int rootY = find(uf, y);
33.     if (rootX == rootY) {
34.         return 0; // 已经在同一个集合
35.     }
36.     // 按秩合并
37.     if (uf->rank[rootX] < uf->rank[rootY]) {
38.         uf->parent[rootX] = rootY;
39.     } else if (uf->rank[rootX] > uf->rank[rootY]) {
40.         uf->parent[rootY] = rootX;
41.     } else {
42.         uf->parent[rootY] = rootX;
43.         uf->rank[rootX]++;
44.     }
45.     return 1; // 合并成功
46. }
48. int main() {
49.     int n;
50.     scanf("%d", &n); // 读取节点数量
52.     UnionFind uf;
53.     initUnionFind(&uf, n);
54.     int redundancyEdge[2] = {0, 0}; // 冗余边的存储
56.     for (int i = 0; i < n; i++) {
57.         int u, v;
58.         scanf("%d %d", &u, &v);
59.         if (!unionSets(&uf, u, v)) {
60.             // 如果这条边连接了已经在同一集合的两个节点，则这条边是冗余的
61.             redundancyEdge[0] = u;
62.             redundancyEdge[1] = v;
63.         }
64.     }
66.     // 输出冗余边
67.     printf("%d %d\n", redundancyEdge[0], redundancyEdge[1]);
69.     return 0;
70. }

复制代码

学习反思

  用于探求冗余边。并查集是一种用于维护聚集的数据结构，通过维护每个节点的父节点和秩来实现。步伐起首界说了一个UnionFind结构体，包罗两个数组，分别用于存储每个节点的父节点和秩。然后界说了初始化并查集的函数initUnionFind，并通过循环将每个节点的父节点设置为自身，并将秩初始化为0。接下来，界说了find函数，用于查找某个节点的根节点。该函数通过递归实现路径压缩，即在查找根节点的过程中将每个节点直接毗连到根节点，以镌汰查找的时间复杂度。然后，界说了unionSets函数，用于归并两个聚集。该函数起首找到两个节点的根节点，并判定它们是否雷同。假如根节点雷同，则阐明这两个节点已经在同一个聚集中，归并失败；否则，根据秩的巨细决定将哪个聚集的根节点毗连到另一个聚集的根节点，并更新秩。在主函数中，起首读取节点的数目n。然后初始化并查集，界说了一个数组redundancyEdge用于存储冗余边的两个节点。接着通过一个循环读取每条边的两个节点u和v，并通过调用unionSets函数将它们归并。假如归并失败，则阐明这条边是冗余的，更新redundancyEdge数组。末了，输出redundancyEdge数组中存储的冗余的两个节点。该步伐的时间复杂度为O(n*logn)，此中n为节点的数目。
  冗余毗连II

  

https://www.programmercarl.com/kamacoder/0109.%E5%86%97%E4%BD%99%E8%BF%9E%E6%8E%A5II.html

  思绪

1. #include <stdio.h>
3. #define MAX_N 1001
5. int main() {
6.     int n;
7.     scanf("%d", &n); // 读取节点和边的数量
9.     int indegree[MAX_N] = {0}; // 每个节点的入度
10.     int parent[MAX_N] = {0}; // 记录每个节点的父节点
11.     int lastRedundantEdge[2] = {0, 0}; // 存储最后找到的冗余边（s,t）
13.     for (int i = 0; i < n; i++) {
14.         int s, t;
15.         scanf("%d %d", &s, &t);
16.         
17.         // 增加t的入度
18.         indegree[t]++;
19.         
20.         // 记录t的父节点是s
21.         parent[t] = s;
23.         // 如果t的入度超过1，则更新冗余边
24.         if (indegree[t] > 1) {
25.             lastRedundantEdge[0] = s; // 冗余边的起点
26.             lastRedundantEdge[1] = t; // 冗余边的终点
27.         }
28.     }
30.     // 输出最后一个找到的冗余边
31.     printf("%d %d\n", lastRedundantEdge[0], lastRedundantEdge[1]);
33.     return 0;
34. }

复制代码

学习反思

  用来探求有向图中的末了一条冗余边的。冗余边指的是参加这条边后，有向图中会形成一个环。算法的思绪是通过纪录每个节点的入度和其父节点，然后遍历每条边，假如某个节点的入度凌驾1，则阐明存在冗余边。末了输出末了找到的冗余边的出发点和尽头。
  这段代码的时间复杂度为O(n)，此中n为节点和边的数目。由于必要遍历一遍全部的边来纪录每个节点的入度和其父节点，并判定是否存在冗余边。