冗余连接
https://www.programmercarl.com/kamacoder/0108.%E5%86%97%E4%BD%99%E8%BF%9E%E6%8E%A5.html
思路
#include <stdio.h>
#include <stdlib.h>#define MAX_N 1000// 并查集结构体
typedef struct {int parent[MAX_N + 1]; // 存储每个节点的父节点int rank[MAX_N + 1]; // 存储每个节点的秩
} UnionFind;// 初始化并查集
void initUnionFind(UnionFind* uf, int n) {for (int i = 1; i <= n; i++) {uf->parent[i] = i; // 每个节点的父节点为自身uf->rank[i] = 0; // 初始秩为0}
}// 查找根节点
int find(UnionFind* uf, int x) {if (uf->parent[x] != x) {// 路径压缩uf->parent[x] = find(uf, uf->parent[x]);}return uf->parent[x];
}// 合并两个集合
int unionSets(UnionFind* uf, int x, int y) {int rootX = find(uf, x);int rootY = find(uf, y);if (rootX == rootY) {return 0; // 已经在同一个集合}// 按秩合并if (uf->rank[rootX] < uf->rank[rootY]) {uf->parent[rootX] = rootY;} else if (uf->rank[rootX] > uf->rank[rootY]) {uf->parent[rootY] = rootX;} else {uf->parent[rootY] = rootX;uf->rank[rootX]++;}return 1; // 合并成功
}int main() {int n;scanf("%d", &n); // 读取节点数量UnionFind uf;initUnionFind(&uf, n);int redundancyEdge[2] = {0, 0}; // 冗余边的存储for (int i = 0; i < n; i++) {int u, v;scanf("%d %d", &u, &v);if (!unionSets(&uf, u, v)) {// 如果这条边连接了已经在同一集合的两个节点，则这条边是冗余的redundancyEdge[0] = u;redundancyEdge[1] = v;}}// 输出冗余边printf("%d %d\n", redundancyEdge[0], redundancyEdge[1]);return 0;
}学习反思
用于寻找冗余边。并查集是一种用于维护集合的数据结构，通过维护每个节点的父节点和秩来实现。程序首先定义了一个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
思路
#include <stdio.h>#define MAX_N 1001int main() {int n;scanf("%d", &n); // 读取节点和边的数量int indegree[MAX_N] = {0}; // 每个节点的入度int parent[MAX_N] = {0}; // 记录每个节点的父节点int lastRedundantEdge[2] = {0, 0}; // 存储最后找到的冗余边（s,t）for (int i = 0; i < n; i++) {int s, t;scanf("%d %d", &s, &t);// 增加t的入度indegree[t]++;// 记录t的父节点是sparent[t] = s;// 如果t的入度超过1，则更新冗余边if (indegree[t] > 1) {lastRedundantEdge[0] = s; // 冗余边的起点lastRedundantEdge[1] = t; // 冗余边的终点}}// 输出最后一个找到的冗余边printf("%d %d\n", lastRedundantEdge[0], lastRedundantEdge[1]);return 0;
}学习反思
用来寻找有向图中的最后一条冗余边的。冗余边指的是加入这条边后，有向图中会形成一个环。算法的思路是通过记录每个节点的入度和其父节点，然后遍历每条边，如果某个节点的入度超过1，则说明存在冗余边。最后输出最后找到的冗余边的起点和终点。
这段代码的时间复杂度为O(n)，其中n为节点和边的数量。因为需要遍历一遍所有的边来记录每个节点的入度和其父节点，并判断是否存在冗余边。