首页 > 其他分享 >一些初赛要用的图论知识

一些初赛要用的图论知识

时间:2022-08-29 20:13:53浏览次数:73  
标签:图论 要用 知识 连通 初赛 顶点

一些初赛要用的图论知识

0x01 无向图与连通图

n个顶点的无向图有n-1个边(以及以上)被称为连通图,而刚好n-1就是一棵树了


0x02 简单图的定义

没有重边和自环的无向连通图被认为是简单图,知道简单图的顶点数可以计算可能的情况。(利用排列组合,也可以暴力手算)


0x03 让连通图变成一棵树

树是n-1,所以需要m-n+1


0x04 环 (ver) (ring)

当每个顶点的度数都是2,就构成环。


0x05 最小生成树

什么是最小生成树?

它可以用Prim和Kruskal得到

作为初赛,我们其实只要掌握就可以了


0x06 完全二叉树


0x7f 未完待续……

标签:图论,要用,知识,连通,初赛,顶点
From: https://www.cnblogs.com/ussr1917/p/16637184.html

相关文章

  • 考研数据结构与算法(七)图论
    @目录一、图的基本概念1.1图的定义1.2基本术语1.2.1有向图1.2.2无向图1.2.3简单图1.2.4多重图1.2.5完全图1.2.6子图1.2.7连通、连通分量、连通图1.2.8强连通1.2.......
  • Highway - 图论 - 树的直径 - 最短路
    http://https://ac.nowcoder.com/acm/problem/52867题目大意有n个城市,城市之间有n-1条无向道路。Bob在任意两个城市之间建造高速公路的花费是这两个城市之间的最短路径......
  • 2022 百度之星初赛 第二场 A
    A题:题目:  双指针,莫队回滚,线段树,归并树都可以过线段树:做法1.给每个节点存当前区间前k大的数做法2.存最大值和它的位置#defineintllconstintN=1e5+10;......
  • 2022百度之星 初赛1 A-B
    A:洞穴不是很懂,但是跑了一遍kruskal就过了//-------------------------代码----------------------------//#defineintllconstintN=200;intn,m;intdist[N]......
  • 2022 百度之星 初赛第一场
    题目都比较简单,OJ和评测机很坑。应该是有若干台评测机,但只有一台是正常速度,最后一题交了34发才过。A洞穴考虑每轮找到当前距离最远的一对点,他们必定都是叶子,任意选其......
  • git在pull/push代码时,需要用户名密码或密钥publickey
    问:git在pull(拉)/push(推)代码时,有的时候需要输入用户名,有的时候需要用密钥,怎么回事呢?答:是因为用gitremote设置远程仓库时候用了htts或ssh不同访问方式造成的。1.用h......
  • 图论-最短路-迷宫2
    迷宫2题目大意这是一个关于二维格子状迷宫的题目。迷宫的大小为N*M,左上角格子座标为(1,1)、右上角格子座标为(1,M)、左下角格子座标为(N,1)、右下角格子座标为(N,M)。......
  • 基于Go语言的xmind读写库,我主要用来把有道云笔记思维导图转为xmind
    项目地址xmind基于go语言的xmind接口使用方法参考:example本库主要加载xmind文件为json结构,保存文件时也用的json结构而不是xml结构本库只做了最基本的主题添加功能......
  • YbtOJ 「图论」第3章 最短路径
    例题1.单源最短路径dij板子。(w36557658原版dij代码!code#include<cmath>#include<queue>#include<cstdio>#include<cstring>#include<iostream>#include<algo......
  • 2022巅峰极客初赛 Misc wp
    一开始做misc1没啥思路,转去misc2,结果一下子给电脑搞废了,太哈人了,以后对注册表都有心理阴影了,还好队友给力,躺进决赛,这里的wp都是今早修完电脑后再复现的。。。easy_Forensi......