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

server/2024/11/25 21:03:33/

冗余连接

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


http://www.ppmy.cn/server/144893.html

相关文章

2024年亚太C题第二版本二问题1求解过程+代码运行以及问题2-4超详细思路分析

2024 亚太地区数学建模竞赛 问题 C 宠物产业及相关产业的发展分析与策略 问题背景 随着人们消费理念的逐步发展&#xff0c;宠物行业作为新兴产业&#xff0c;凭借着经济的快速发展和人均收入的不断提高&#xff0c;逐渐在全球范围内积聚动能。1992年&#xff0c;中国小动…

OpenAI震撼发布:桌面版ChatGPT,Windows macOS双平台AI编程体验!

【雪球导读】 「OpenAI推出ChatGPT桌面端」 OpenAI重磅推出ChatGPT桌面端&#xff0c;全面支持Windows和macOS系统&#xff01;这款新工具为用户在日常生活和工作中提供了前所未有的无缝交互体验。对于那些依赖桌面端进行开发工作的专业人士来说&#xff0c;这一更新带来了令人…

node.js中使用express.static()托管静态资源

express.static()定义 express.static(root, [options])是一个中间件函数&#xff0c;负责为Express应用提供静态资源服务。它允许你指定一个或多个目录作为静态资源的根目录&#xff0c;当客户端请求这些资源时&#xff0c;Express会查找并返回对应的文件。 安装express npm i…

如何在 .gitignore 中仅保留特定文件:以忽略文件夹中的所有文件为例

在日常的开发工作中&#xff0c;使用 Git 来管理项目是不可或缺的一部分。项目中的某些文件夹可能包含大量的临时文件、生成文件或不需要版本控制的文件。在这种情况下&#xff0c;我们通常会使用 .gitignore 文件来忽略这些文件夹。然而&#xff0c;有时我们可能希望在忽略整个…

Dubbo Golang快速开发Rpc服务

开发 RPC Server & RPC Client 基于 Dubbo 定义的 Triple 协议&#xff0c;你可以轻松编写浏览器、gRPC 兼容的 RPC 服务&#xff0c;并让这些服务同时运行在 HTTP/1 和 HTTP/2 上。Dubbo Go SDK 支持使用 IDL 或编程语言特有的方式定义服务&#xff0c;并提供一套轻量的 …

Selenium 使用指南:从基础到反爬虫的实践

掌握Selenium 文章目录 掌握Selenium复杂动态网页解决方案Selenium简介Selenium chromedriver 安装打开自动化浏览器初始化机器人访问url——browser.get(url)全屏打开网页——browser.maximize_window()关闭窗口——browser.close()指定selenium参数需要的库网页元素定位获取…

oracle的静态注册和动态注册

oracle的静态注册和动态注册 静态注册&#xff1a; 静态注册 : 指将实例的相关信息手动告知 listener 侦 听 器 &#xff0c; 可以使用netmgr,netca,oem 以及直接 vi listener.ora 文件来实现静态注册&#xff0c;在动态注册不稳定时使用&#xff0c;特点是&#xff1a;稳定&…

ssm基于bs的企业合同管理系统

摘要 企业合同管理系统是一种旨在帮助企业高效管理各类合同的软件工具。该系统能够实现合同的电子化存储、快速检索和版本控制&#xff0c;简化审批流程。通过这一系统&#xff0c;企业能够确保合同执行的合规性&#xff0c;降低法律风险&#xff0c;同时提升工作效率和管理水…