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

冗余连接

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 1001

int 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的父节点是s
        parent[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为节点和边的数量。因为需要遍历一遍所有的边来记录每个节点的入度和其父节点，并判断是否存在冗余边。