当前位置：首页 > news >正文

算法竞赛备赛——【图论】链式前向星

news 来源：原创 2025/8/23 3:11:53

图论

图的存储方式：

通用的三种：邻接矩阵、邻接表、边集数组

有向图：十字链表

无向图：多重邻接表

刷题常用：邻接矩阵、链式前向星（邻接表变形）

链式前向星

算法题常用:

邻接矩阵、二维vector模拟邻接表、链式前向星

n个点 m条边 m>nlogn算稠密图 m<nlogn算稀疏图

稠密图：邻接矩阵 O(n^2)

稀疏图：邻接表---->二维vector（无权）/链式前向星（带权） O(n+m) （边多了连的多不合适）

无权无向图

#include <bits/stdc++.h>
using ll=long long;
using namespace std;
const int N=5e4+5; //无权无向图 ---->二维vector 模拟邻接表 多用于存无权图
int n,m;vector<vector<int>> g;
int v[105];void dfs(int x){if(v[x]) return;printf("%d ",x); v[x]=1;int y;for(int i=0;i<g[x].size();++i){y=g[x][i];dfs(y);}
}int main(){cin>>n>>m;g.resize(n+1);int x,y;for(int i=1;i<=m;++i){cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}for(int i=1;i<=n;++i){if(v[i]==0) dfs(i);}return 0;
}
/*输入样例 
4 5
1 2
1 4
2 3
2 4
3 4
*/

有权无向图

#include <bits/stdc++.h>
using ll=long long;
using namespace std;
const int N=5e4+5; //带权无向图 ---->链式向前星 ----> 静态链表模拟邻接表 
int n,m;
int head[105]; 
int v[105]; 
struct edge{int to;//该边的终点 int w;//该边的权值 int nex;//和该边同起点的另一条边的下标 
}e[10005];//边的条数最大为n*(n-1) int cnt=0;
void add(int x,int y,int wi){//x--wi->ye[cnt].to=y;e[cnt].w=wi;//模拟链表的头插法 e[cnt].nex=head[x];head[x]=cnt;cnt++;
}void dfs(int x){if(v[x]) return ;printf("%d ",x);v[x]=1;for(int i=head[x];i!=-1;i=e[i].nex){//枚举x所有出边 找x的临界点 int y=e[i].to;dfs(y); }
}int main(){memset(head,-1,sizeof head);cin>>n>>m;int x,y,wi;for(int i=1;i<=m;++i){cin>>x>>y>>wi;add(x,y,wi);add(y,x,wi);}for(int i=1;i<=n;++i){if(v[i]==0) dfs(i);}return 0;
}
/*输入样例 
4 5
1 2 5
1 4 3
2 3 8
2 4 12
3 4 9
*/

算法竞赛备赛——【图论】链式前向星

图论图的存储方式： 通用的三种：邻接矩阵、邻接表、边集数组有向图：十字链表无向图：多重邻接表刷题常用：邻接矩阵、链式前向星（邻接表变形） 链式前向星算法题常用: 邻接矩阵、二维vector模…...

编程日记 2025/8/23 3:11:53

JAVA_类和对象

目录 1.面向对象的初步认知 1.1.什么是面向对象 1.2.面向对象与面向过程 2.类的定义和使用 2.1.简单认识类 2.2类的定义格式 2.3.练习学生类动物类（可爱猫猫🐱） 3.类的实例化 3.1.什么是实例化 3.2.类和对象的说明 4.this引用…...

编程日记 2025/8/17 22:22:40

高频面试题（含笔试高频算法整理）基本总结回顾65

干货分享，感谢您的阅读！ （暂存篇---后续会删除，完整版和持续更新见高频面试题基本总结回顾（含笔试高频算法整理）） 备注：引用请标注出处，同时存在的问题请在相关博客留言…...

编程日记 2025/8/23 3:11:52

数据库系统-数据库控制

并发控制事务的ACID特性： 原子性（Atomicity）：事务包含的所有操作要么全部成功（commit提交），要么全部失败（rollback回滚）一致性（Consistency）&a…...

编程日记 2025/8/23 3:10:12

Python Cookbook-5.3 根据对象的属性将对象列表排序

任务需要根据各个对象的某个属性来完成对整个对象列表的排序。解决方案 DSU方法仍然一如既往地有效: def sort_by_attr(sed,attr):intermed [ (getattr(x,attr),i,x) for i,x in enumerate(seg)]intermed.sort()return [ x[-1] for x in intermed def sort_by_attr_inpl…...

编程日记 2025/8/22 5:12:08

Java MCP SDK 开发笔记（一）

MCP 简介 AI 大模型诞生之初，其高度模拟人的对话之能力惊为天人。但我们肯定不希望止步于此—— 工具化就是我们希望 AI 能够完成的目标，由此可以从单纯的对话发展为代替繁复人力的“干活”。这条道路上毋庸置疑 AI 大模型任重道远。而 MCP(Model Contr…...

编程日记 2025/8/21 10:47:00

AF3 OpenFoldDataLoader类_prep_batch_properties_probs方法解读

AlphaFold3 data_modules 模块的 OpenFoldDataLoader 类的 _prep_batch_properties_probs 方法是为每个批次数据准备 recycling 维度的概率分布。它将根据配置文件中的设定为每个批次数据生成 recycling 轮次的概率分布，并存储到 prop_probs_tensor 中，用于后续抽样选择特定…...

编程日记 2025/8/21 23:57:56

寻找字符串数组中的最长共同前缀字符串

问题描述：给定一个字符串数组 strs，编写一个函数来找到这些字符串的最长公共前缀字符串，如果没有则返回空字符串"" 算法思路横向扫描法： 从数组的第一个字符串开始，逐个和后面的字符串比较，逐…...

编程日记 2025/8/20 2:27:07

leetcode_数组 56. 合并区间

56. 合并区间以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。示例 1： 输入：int…...

编程日记 2025/8/19 1:49:14

Jenkins学习（B站教程）

文章目录 1.持续集成CI2.持续交付CD3.持续部署4.持续集成的操作流程5.jenkins简介6.后续安装部署，见视频 bilibili视频 Jenkins是一个开源的、提供友好操作界面的持续集成(CI)工具，起源于Hudson（Hudson是商用的），主要用…...

编程日记 2025/8/22 16:49:44

学习笔记—C++—类和对象（一）

目录类和对象类的定义类定义格式访问限定符类域实例化实例化概念对象的大小 this指针 C和C语言实现Stack对比类和对象类的定义类定义格式 ● class为定义类的关键字，Stack为类的名字，{}中为类的主体，注意类定义结束时后…...

编程日记 2025/8/21 8:35:33

PyTorch 深度学习 || 6. Transformer | Ch6.3 Transformer 简单案例

1. 简单案例这个代码是一个简单的 Transformer 模型的实现，这个例子展示了一个基本的序列到序列（seq2seq）任务，比如将一个数字序列转换为另一个数字序列。可以用于学习和理解 Transformer 的基本结构和工作原理。 import torch import torch.nn as nn import math# 位置…...

编程日记 2025/8/22 11:06:40

体育风暴篮球足球体育球员综合资讯网站模板

源码名称：篮球足球体育球员综合资讯网站模板开发环境：帝国cms7.5 空间支持：phpmysql 带软件采集，可以挂着自动采集发布，无需人工操作！ 演示地址：https://www.52muban.com/shop/184016.html …...

编程日记 2025/8/23 3:11:53

Visual Studio Code SSH 连接超时对策（ keep SSH alive）

文章目录问题解决方法一：配置服务端关于ClientAliveInterval和ClientAliveCountMax1、打开终端，打开SSH配置文件：输入以下命令：2、打开配置文件后，添加以下内容：3、添加后，Esc按 <Enter>…...

编程日记 2025/8/19 2:55:04

Docker容器中的ubuntu apt update报错解决办法

问题现象 # apt update Get:1 http://archive.ubuntu.com/ubuntu noble InRelease [256 kB] Get:2 http://security.ubuntu.com/ubuntu noble-security InRelease [126 kB] Err:2 http://security.ubuntu.com/ubuntu noble-security InRelease At least one invalid signa…...

编程日记 2025/8/22 5:12:18

CV - 目标检测

物体检测目标检测和图片分类的区别： 图像分类（Image Classification） 目的：图像分类的目的是识别出图像中主要物体的类别。它试图回答“图像是什么？”的问题。输出：通常输出是一个标签或一组概率值&am…...

编程日记 2025/8/23 3:11:51

linux提权 corn 提权

corn提权 corn的基本使用方法 corn的作用就是可以定时的完成一下任务（如备份一下log 或者清除一下日志文件这些就是运维人员用的） 先找一下定时任务的工作表 cat /bin/corntab 这个是普通用户我们直接看都看不了说明什么说明这个是root高权限执…...

编程日记 2025/8/23 3:10:13

1Panel安装失败国内docker安装失败

本文仅针对学习交流，只为了帮助计算机相关专业大学生个人技能实操而记录非学习目的严禁学习！！！否则后果自负 1、离线安装1Panel（不需要手动安装docker，离线安装包里包括了docker） 离线包下载地…...

编程日记 2025/8/21 16:09:47

Excel + VBA 实现“准实时“数据的方法

Excel 本身是静态数据处理工具，但结合 VBA（Visual Basic for Applications）可以实现准实时数据更新，不过严格意义上的实时数据（如毫秒级刷新）仍然受限。以下是详细分析： 1. Excel + VBA 实现“准实时”数据的方法 (1) 定时刷新（Timer 或 Application.OnTime） Appl…...

编程日记 2025/8/23 2:15:27

请问你怎么看待测试，指导哪些测试的类型，有用过哪些测试方法？

作为深耕测试领域多年的博主，我始终认为测试是软件质量的守护者，更是推动研发流程优化的催化剂。以下从测试认知、分类体系到实战方法论，结合具体案例为你系统拆解：一、测试的本质认知测试≠找 Bug，而是通过系统性验证回答三个核心问题：软件是否符合用户需求？系统在…...

编程日记 2025/8/22 14:37:13

详解 Redis repl_backlog_buffer（如何判断增量同步）

一、repl_backlog_buffer 复制积压缓冲区（Replication Backlog Buffer） 是一个环形内存区域（Ring Buffer），用于临时保存主节点最近写入的写命令，以支持从节点断线重连后的增量同步。 1.1 三个复制偏移量 …...

编程日记 2025/8/20 23:51:34

工业操作系统国产化替代的战略路径与挑战分析

一、政策背景与战略意义工信部提出的 2027 年替换 80 万套工业操作系统计划，是中国制造业向智能化转型的核心举措。该政策旨在通过国产化替代，解决工业领域 “缺芯少魂” 的问题，构建自主可控的工业软件生态体系。当前，中国工业操…...

编程日记 2025/8/20 11:39:58

JMeter接口性能测试从入门到精通

前言： 本文主要介绍了如何利用jmter进行接口的性能测试 1.在测试计划中添加线程组 1.1.线程组界面中元素含义如果点击循环次数为永远： 2.添加HTTP取样器 2.1.填写登录接口的各个参数 2.2.在线程组下面增加查看结果树请求成功的情况： 请求…...

编程日记 2025/8/17 22:20:59

WinForm真入门(9)——RichTextBox控件详解

WinForm中RichTextBox控件详解：从基础到高级应用上一文中笔者重点介绍了TextBox控件的详细用法，忘记的请点击WinForm真入门(8)——TextBox控件详解，那么本文中的RichTextBox与TextBox有什么区别吗，光看名字的话，多了…...

编程日记 2025/8/20 14:01:45

Linux : 内核中的信号捕捉

目录一前言二信号捕捉的方法 1.sigaction()编辑 2. sigaction() 使用三可重入函数四 volatile 关键字一前言如果信号的处理动作是用户自定义函数,在信号递达时就调用这个函数,这称为捕捉信号。在Linux: 进程信号初识-CSDN博客这一篇中已经学习到了一种信号…...

编程日记 2025/8/18 0:02:29

Linux 字符串截取#与%

在Linux的Shell脚本中，#和%用于字符串截取，通过通配符模式匹配删除部分内容批量修改文件名技巧：Linux下#、##、%、%%符号操作详解-CSDN博客从左截取（# 和 ##） #：删除最短匹配左侧内容。 ##&#xff1a…...

编程日记 2025/8/18 0:40:17

Android学习总结之自定义View实战篇

场景一：自定义进度条在很多应用中，我们会看到一些独特样式的进度条，接下来就实现一个简单的圆形进度条。实现思路继承 View 类。重写 onDraw 方法，在该方法里使用 Canvas 和 Paint 来绘制圆形进度条。提供更新进度的方法。 …...

编程日记 2025/8/22 12:00:21

C++ STL 详解 ——list 的深度解析与实践指南

在 C 的标准模板库（STL）中，list作为一种重要的序列式容器，以其独特的双向链表结构和丰富的操作功能，在许多编程场景下发挥着关键作用。深入理解list的特性与使用方法，能帮助开发者编写出更高效、灵活的代码…...

编程日记 2025/8/20 7:18:14

open函数的概念和使用案例

open 是 Linux/Unix 系统中用于打开或创建文件的系统调用，返回一个文件描述符（File Descriptor），后续可通过该描述符进行文件读写等操作。以下是其核心概念和使用案例的详细说明： 1. 核心概念作用：打开或…...

编程日记 2025/8/17 23:39:36

整理一些大模型部署相关的知识

不一定有什么用, 不经常用还会忘掉. 之前被人问到一次,脑子卡壳回答不出要点, 非常尴尬! 在此记录一下使用心得, 偶尔回来翻看! 一并行方式 1.1 数据并行 (Data Parallelism) 主要用于模型训练阶段, 即将多个完整的模型副本分布到多个gpu上, 每个gpu运行一部分数据数据, 每个…...

编程日记 2025/8/21 17:31:39

算法刷题记录——LeetCode篇(2.10) [第191~200题](持续更新)

更新时间：2025-04-04 算法题解目录汇总：算法刷题记录——题解目录汇总技术博客总目录：计算机技术系列博客——目录页优先整理热门100及面试150，不定期持续更新，欢迎关注！ 198. 打家劫舍你是一个专业的…...

编程日记 2025/8/21 2:15:43

蓝桥杯备赛 Day 19 加练dfs

是否需要回溯? 输入参数有哪几个(当前dfs和下一个dfs什么会变?)？ 是否需要返回值? 一.1158: 八皇后 P1158 - 八皇后 - New Online Judge (ecustacm.cn) 学习: 1.dfs输入为层数，即行号i，因为是每行只放一个，下一个dfs就是i1 2…...

编程日记 2025/8/17 23:16:22

蓝桥杯-卡java排序

问题描述本题是一道针对 Java 中 Arrays.sort 的题目，因此只有一个数据，该数据可以把 int 类型的数组在使用 Arrays.sort 后卡成 O(n2)O(n2)。给定一个有 nn 个正整数的序列 aa，你需要将其升序排序后输出。输入格式第一行输入一个正整…...

编程日记 2025/8/21 12:25:00

内存管理模块

在 Linux 内核中，内存管理是一个复杂而关键的组成部分。内核空间的虚拟地址被划分为多个区域，每个区域有其特定的用途和映射机制。本文将详细介绍直接映射区（Direct Mapping Area）、vmalloc 区、永久内核映射区（Perma…...

编程日记 2025/8/20 2:27:09

Spring RestTemplate修仙指南：从HTTP萌新到请求大能的终极奥义

各位在Spring生态摸爬滚打的道友们！今天要解锁的是Spring官方御用HTTP法宝——RestTemplate！这货堪称Java界的"御剑飞行术"，虽然官方已推荐WebClient接棒，但江湖上仍有80%项目在用这员老将！准备好一键起飞了…...

编程日记 2025/8/21 11:09:19

cpp经典数论问题

题目如下思路代码如下...

编程日记 2025/8/18 0:02:49

Redis 线程模型：单线程也能快如闪电？

目录一、核心思想：快刀斩乱麻的“单线程”高手 🦸‍♂️二、为什么是“单线程”？🤔三、单线程如何做到高性能？✨ “I/O 多路复用”是关键！四、真的一直都只有“一个线程”吗？并不完全是&#x…...

编程日记 2025/8/20 18:09:31

游戏引擎学习第208天

运行游戏并回顾我们的情况今天，我们将继续完成之前中断的调试输出工作。最近的工作偏离了一些，展示了如何进行元编程的实践，主要涉及了一个小的解析器。尽管这个解析器本身是一个玩具，但它展示了如何完成一个完整的循环&#xf…...

编程日记 2025/8/20 1:37:05

JavaScript箭头函数介绍（=＞）（箭头函数不绑定自己的this，而是继承上下文的this；不能用于造函数）JavaScript =＞

文章目录 JavaScript箭头函数全解析箭头函数的基本语法简洁语法特性隐式返回值对象字面量返回词法绑定的this不适用箭头函数的场景对象方法构造函数DOM事件处理高级用法在数组方法中的应用链式调用柯里化函数性能考量1. 作为回调函数时减少创建闭包的开销2. 简化代码结构&am…...

编程日记 2025/8/20 4:38:16

数据对象：DTO、DO、PO和 BO的区别和关系

在Java开发中，DTO（Data Transfer Object）、DO（Domain Object）、PO（Persistent Object）和BO（Business Object）是常用的数据对象概念，下面为你详细介绍并给出简…...

编程日记 2025/8/21 1:56:15

Java内存模型详解：堆、栈、方法区

1. 堆（Heap） 作用：存放所有对象实例及数组，是垃圾回收的主要区域。结构： 新生代（Young Generation）： Eden区：新创建的对象首先分配在此。 Survivor区（From…...

编程日记 2025/8/21 19:21:39

ubuntu 20.04 编译运行LeGo_LOAM 跑数据集并且保存pcl文件

1.搭建文件目录,clone代码,编译 mkdir -p Lego_LOAM/src cd Lego_LOAM/src git clone https://github.com/RobustFieldAutonomyLab/LeGO-LOAM.git cd .. catkin_make -j1 错误1：: fatal error: opencv/cv.h: 没有那个文件或目录 13 | #include <opencv/cv.h…...

编程日记 2025/8/20 11:49:54

CMake使用教程

CMake是开源、跨平台的构建工具，可以让我们通过编写简单的配置文件去生成本地的Makefile，这个配置文件是独立于运行平台和编译器的，这样就不用亲自去编写Makefile了，而且配置文件可以直接拿到其它平台上使用，无需修改，非常方便。使用命令行执行CMakeLists.txt，对文件进…...

编程日记 2025/8/21 10:56:07

快速上手Linux进程管理

一.理解进程和线程 1.1 什么是进程它表示一个正在执行的程序实例。在操作系统中，进程是系统进行资源分配和调度的基本单位。每个进程都有自己独立的内存空间、代码、数据和系统资源，如打开的文件、使用的硬件设备等。进程的主要特点包括&#xff1a…...

编程日记 2025/8/21 13:50:38

pytorch框架实现cnn四种天气图片多分类问题-添加dropout和bn层

目录 1.导包 2.加载数据、拼接训练、测试文件夹 3. 查看当前目录下的所有文件名，以列表的形式输出 4.原数据集dataset中存在的数据的目标类别 5.创建train和test目录及其需要分类的子文件夹 6.使用torchvision 的transforms进行数据预处理 6.1数据统一缩放resize、To…...

编程日记 2025/8/21 17:27:01

swift-11-init、deinit、可选链、协议、元类型

一、required 二、属性观察器三、可失败初始化器可以用init!定义隐式解包的可失败初始化器可失败初始化器可以调用非可失败初始化器，非可失败初始化器调用可失败初始化器需要进行解包如果初始化器调用一个可失败初始化器导致初始化失败 ，那么整个初…...

编程日记 2025/8/21 17:03:32

【力扣hot100题】（062）搜索插入位置

感觉自己对二分法还是没有很好掌握，主要在于边界问题，只会基本的搜索，如果要搜索比目标值大的第一个索引或者比目标值小的最后一个索引（或者换一些花里胡哨的题目）就完全不会了。 class Solution { public:int search…...

编程日记 2025/8/22 11:55:23

TCPIP详解卷1协议三链路层

3.1——以太网和IEEE802局域网/城域网标准以太网这个术语通常指一套标准，由DEC，Intel公司和Xerox公司在1980年首次发布，并在1982年加以修订。第一个常见格式的以太网，目前被称为10Mb/s以太网或共享以太网。它被IEEE采纳为802.3标…...

编程日记 2025/8/22 17:54:49

以太网安全

前言： 端口隔离可实现同一VLAN内端口之间的隔离。用户只需要将端口加入到隔离组中，就可以实现隔离组内端口之间的二层数据的隔离端口安全是一种在交换机接入层实施的安全机制，旨在通过控制端口的MAC地址学习行为，确保仅授权设备能…...

编程日记 2025/8/19 4:36:53

linux如何查看当前系统的资源占用情况

在 Linux 系统中，有多个命令可以查看当前系统的资源占用情况。以下是一些常用的命令及其说明： 1. 查看内存使用情况：free free -h-h 参数表示以人类可读的格式显示（如 MB, GB）。输出示例： to…...

编程日记 2025/8/17 22:28:12

图论

链式前向星

相关文章：