目录DAG求食物链数DAG求路径长度和路经总和题目：最大食物链解法一： 解法二：记忆化题目：游走思路：                           题目：最大食物链        解法一：topo排序          我们标记f[i]是被f[x]捕食的点对应的类食物链数不难得出：f[x]=∑(f[i])  首先从生产者开始，每去掉一个被捕食的点，那么相邻捕食者就要加上去掉点的类食物链数，但是我们还需要找到出度为0的消费者。所以这道题，我们要同时记录入度，还有出度（其实单纯的topo排序就用不上出度，记录出度是为了找食物链结尾的个数）            #includeusingn

概论图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年,凯莱在计数烷CnH2n+2的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈、近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学，生物遗传学、心理学、经济学、社会学等学科中。图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直

目录10.1GraphsandGraphModels(图和图模型)10.2GraphTerminologyandSpecialTypesofGraphs(图的术语和几种特殊图)1.基础概念2.度（degree）（1）无向图中一个顶点v的度是这个点相关的边的数量，写作deg(v)（2）握手定理 （3）出度和入度 3.图的分类（1）圈图（Cycles） （2）轮图（3）n维超立方体（4）二部图（BipartiteGraphs）4.子图（1）概念（2）导出子图 （3）删除边和添加边（4）边收缩（edgecontraction）（5）图合并10.3RepresentingGraphsandGraphI

🎃个人专栏：🐬算法设计与分析：算法设计与分析_IT闫的博客-CSDN博客🐳Java基础：Java基础_IT闫的博客-CSDN博客🐋c语言：c语言_IT闫的博客-CSDN博客🐟MySQL：数据结构_IT闫的博客-CSDN博客🐠数据结构：​​​​​​数据结构_IT闫的博客-CSDN博客💎C++：C++_IT闫的博客-CSDN博客🥽C51单片机：C51单片机（STC89C516）_IT闫的博客-CSDN博客💻基于HTML5的网页设计及应用：基于HTML5的网页设计及应用_IT闫的博客-CSDN博客​​​​​​🥏python：python_IT闫的博客-CSDN博客🐠离散数学：离散数学_IT闫的博客-

二部(分)图定义：二部图是一种特殊的图，可以将图的节点分为2个几个，且每个集合中，节点之间没有关联。大概长这个样子：理论判断：图G中至少存在两个点，且图中所有回路的长度均为偶数。任何无回路的的图均是二分图。判断图为二部图的方法：染色法定义：对每一个顶点dfs，对本身染色为1，对其邻点染色成2，若存在其本身与其相邻的节点的颜色相同，则不是二分图，否则是二分图。例题：AcWing860.染色法判定二分图代码如下：#includeusingnamespacestd;intn,m;constintN=1e5+11;vectorint>e[N];intcolor[N];booldfs(intx,intc

》》》算法竞赛/***@file*@authorjUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 **@brief一直在竞赛算法学习的路上**@copyright2023.9*@COPYRIGHT 原创技术笔记：转载需获得博主本人同意，且需标明转载源*@languageC++*@Version1.0还在学习中*/UpDataLog👆2023.9.27更新进行中Statement0🥇一起进步Statement1💯有些描述是个人理解，可能不够标准，但能达其意技术提升站点文章目录》》》算法竞赛技术提升站点21-1树的直

一.定义​ 强连通分量（StronglyConnectedComponents，简称SCC）是图论中的一个概念，用于描述有向图中的一组顶点，其中任意两个顶点之间都存在一条有向路径。换句话说，对于图中的任意两个顶点u和v，如果存在一条从u到v的有向路径，同时也存在一条从v到u的有向路径，那么u和v就属于同一个强连通分量。强连通分量在许多图算法中都有重要的应用，比如强连通分量的计算可以用于解决图的可达性问题、强连通分量的缩点可以用于求解最小生成树等。注意：强连通分量是有向图！ 二.例题P2863[USACO06JAN]TheCowPromS-洛谷|计算机科学教育新生态(luogu.com.cn)三

弗洛伊德算法：弗洛伊德算法本质是动态规划，通过添加点进如可选择的点组成的集合的同时更新所有点之间的距离，从而得到每两个点之间的最短距离。初始化：创建一个二维数组dist，其中dist[i][j]表示从节点i到节点j的最短路径的权重。将对角线上的元素初始化为0，表示节点到自身的距离。如果存在直接相连的边，则将dist[i][j]初始化为这些边的权重；否则，初始化为一个大数表示无穷大。三重循环：对于每一对节点(i,j)，以及所有可能的中间节点k，进行三重循环：plaintextCopycodeforkfrom1ton: forifrom1ton:  forjfrom1ton:   dist[i][

图论（GraphTheory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些实体之间的某种特定关系，用点代表实体，用连接两点的线表示两个实体间具有的某种关系。相比矩阵、张量、序列等结构，图结构可以有效建模和解决社会关系、交通网络、文法结构和论文引用等需要考虑实体间关系的各种实际问题。因此，为了能够有效利用图结构这种工具，我们必须要对图的定义、类型和性质有一定的认识。 概念图是由顶点（vertex）和边（edge）组成的数据结构如下图：节点（node）用红色标出，通过黑色的边（edge）连接。图可用于表示：社交网络网页生物网络…

文章目录一、图的基本概念二、图的连通性三、树四、E图与H图五、对集与独立集六、平面图与网络流一、图的基本概念1、基本概念2、顶点的度概念，有关定理及推论（握手定理），度序列的概念及相关结论，根据度序列画图（相互），特别是画简单图。3、子图、补图、完全图、二分图等特殊图，概念、判定及应用；判断二分图的几种方法。4、矩阵表示，邻接矩阵、关联矩阵、度矩阵、其他矩阵；根据图构造矩阵，根据矩阵画图（判断顶点、边）；图的特征多项式、特征值、图的谱。广义邻接矩阵。5、有向图的基本概念，涉及矩阵表示、连通、树形图、网络流。二、图的连通性1、概念，如途径、迹、路、圈，图论距离；二分图判定的奇圈法。2、连通，连通