图论题单

图论1:

题目链接: 2021-03-14 2021年度训练联盟热身训练赛第二场 F: Interstellar Love

题目大意: 给出一张图，输出图中有多少个连通块，再输出有多少个带环的连通块

解题思路: 单向边建图，并查集存储连通块的个数，每个连通块进行搜索看连通块里面的边的个数与点的个数的关系，边大于等于点则必有环(包括自环)

code: https://paste.ubuntu.com/p/rBQcWVV8K2/

图论2：

题目链接: 2022-07-09 acwing第59场周赛 C: AcWing 4493. 环形连通分量

题目大意: 给出一张图，输出其中标准环的个数，标准环定义，每个点度为2并且最少由三个点组成

解题思路: 双向存边存下来每个点的度数进行搜索，判断度是否为2要是搜到的下个点已经被搜过，看一下他是否是当前点的父亲，不是的话证明已经搜回一开始的起点且度全为2，答案加一

code: https://paste.ubuntu.com/p/vcdJgkkMQn/

图论3:

题目链接: 2021-06-06 第三届太原理工大学程序设计竞赛新生赛(重现赛) K: 库特莉亚夫卡的排序

题目大意: 给出一串数字，下面给出m对可以交换的数字位置对，请判断通过任意次交换能否将该串叫换成递增的串

解题思路: 同一个联通块里面可以任意交换的，因为要递增连通块里面一定满足递增，每个连通块都递增最后判断整体是否递增就行了，用图搜索出连通块进行排序归位

tips: 树的终点判断 if(j == f) contionue 但是图要加上判断是否搜到过当前点 if(j == f || vis[j]) continue 因为树不会搜到已经搜过的点，但是图会

code: https://paste.ubuntu.com/p/kG4DppK3bN/

并查集写法: 传送门

图论4:

题目链接: 2022-07-23 "蔚来杯"2022牛客暑期多校训练营2 D: Link with Game Glitch

题目大意: 一次给出两个物品四个数a, b, c, d代表a个b物品可以换c个d物品问给b~d路径乘上一个最大为多大的摩擦系数可以使得不能造成换无限物品的可能出现

解题思路: 二分出我们要找的答案，这个答案是在0-1之间的，因为乘积太大故先取对数把边权相乘变为边权相加，这样的话当摩擦系数最大取多大的时候可以将某个变换关系的路径上面的值相乘变为1取对数之后相当于求最大的摩擦系数使得不存在正环，判负环先将距离设置为0x3f3f3f3f一直往小更新，判正环先将距离设置为0往大更新

code: https://paste.ubuntu.com/p/J9WPqJnXmB/