有趣的地方

有趣的地方

图论知识汇总

算法可以发掘本质,如:
一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二,有无限多1X2和2X1的骨牌,某个棋盘若干格子坏了,如何在没有坏的格子放足够多骨牌。
三,某个单色图,1表示前前景,0表示后景色。每次操作可以将一个1,变成0。如何在最少得操作情况下,使得没有两个1相邻(四连通)。
四,若干路人,有些人是熟人,如何选出最多的人参加实验。为了避免熟人影响实验的效果,参加的人不能是熟人。
一二是二分图的最大匹配,三是二分图的最小点覆盖,四是二分图最大独立集。 而这三者是等效问题。

深度优先搜索

C++深度优先(DFS)算法的应用:2920收集所有金币可获得的最大积分
C++深度优先搜索的应用:在树上执行操作以后得到的最大分数
C++深度优先搜索(DFS)算法的应用:树中可以形成回文的路径数
【深度优先】LeetCode1932:合并多棵二叉搜索树
【剪枝】【广度优先】【深度优先】488祖玛游戏

【归并排序】【图论】【动态规划】【 深度优先搜索】1569将子数组重新排序得到同一个二叉搜索树的方案数
【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率
【图论】【状态压缩】【树】【深度优先搜索】1617. 统计子树中城市之间最大距离
【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目
【图论】【树形dp】【深度优先搜索】2538. 最大价值和与最小价值和的差值
【深度优先搜索】【图论】【树】2646. 最小化旅行的价格总和
【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II

【树】【图论】【树路径】【深度优先搜索】2867. 统计树中的合法路径数目
【动态规划】【树形dp】【深度优先搜索】LCP 26. 导航装置
【深度优先搜索】【树】【C++算法】2003. 每棵子树内缺失的最小基因值
【树】【因子数】【数论】【深度优先搜索】2440. 创建价值相同的连通块
【树】【异或】【深度优先】【DFS时间戳】2322. 从树中删除边的最小分数
【深度优先】【图论】【C++算法】2045. 到达目的地的第二短时间

广度(宽度)优先搜索

C++算法:广度优先搜索(BFS)的原理和实现
利用广度优先或模拟解决米诺骨牌
【动态规划】【广度优先】LeetCode2258:逃离火灾
【动态规划】【广度优先搜索】【逆向思考】【单调向量】2617 网格图中最少访问的格子数
【剪枝】【广度优先】【深度优先】488祖玛游戏
【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径
【广度优先搜索】【拓扑排序】【C++算法】913. 猫和老鼠
【广度优先搜索】【网格】【割点】1263. 推箱子
【深度优化】【广度优先】【状态压缩】864. 获取所有钥匙的最短路径
【字符串】【括号匹配】【广度优先】301. 删除无效的括号
【广度优先搜索】【堆】【C++算法】407. 接雨水 II
【广度优先搜索】【C++算法】1900. 最佳运动员的比拼回合
【图论】【广度优先】【 并集查找】2092 找出知晓秘密的所有专家

并集查找

C++二分查找或并集查找:交换得到字典序最小的数组
【图论】【并集查找】【C++算法】928. 尽量减少恶意软件的传播 II
【广度优先搜索】【图论】【并集查找】2493. 将节点分成尽可能多的组

最短路径

C++算法:多源最短路径的原理及实现
C++算法:存在负权边的单源最短路径的原理和实现
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
【单源最短路 图论】882. 细分图中的可到达节点
暂无题解:
2203

最小生成树

【图轮】【 最小生成树】【 并集查找】1489. 找到最小生成树里的关键边和伪关键边

拓扑排序

【图论】【拓扑排序】1857. 有向图中最大颜色值
【拓扑排序】【 图论】1203. 项目管理
【图论】【树】 【拓扑排序】2603. 收集树中金币
【逆向思考 】【拓扑排序】1591. 奇怪的打印机 II
暂无题解:2050 2392

换根法
【深度优先搜索】【C++算法】834 树中距离之和
【图论】【深度优先搜索】【换根法】2858. 可以到达每一个节点的最少边反转次数
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目
树的路径
【深度优先搜索】【树】【状态压缩】2791. 树中可以形成回文的路径数

欧拉路径、欧拉环

【深度优先搜索】【图论】【推荐】332. 重新安排行程
【数学】【深度优先搜索】【图论】【欧拉环路】753. 破解保险箱
【欧拉回路】【图论】【并集查找】765. 情侣牵手
暂无题解:2097

基环树

基环树,也是环套树,是一种有 n 个点 n 条边的图,简单地讲就是树上在加一条边。它形如一个环,环上每个点都有一棵子树的形式。
基环内向树:每个点出度为1(因此每个环上点的子树,儿子指向父亲)
基环外向树:每个点入度为1(因此每个环上点的子树,父亲指向儿子)
基环树的关键就是找到环,可以先把环当作这个无根树的 “根” ,也就是把环当成一个点(先不管它),这样一颗基环树就变成了一个普通的树,然后我们先按照解决普通树的方法对“根”的所有子树依次处理求解答案

【图论】【基环内向树】【广度优先】【深度优先】2127. 参加会议的最多员工数

暂无题解:
2876 有向图访问计数 基环内向树
2360图中的最长环

树上倍增

【树上倍增】2836在传球游戏中最大化函数值
【深度优先】【树上倍增 】2846. 边权重均等查询

扩展内容难道较大

二分图(染色判定、最大匹配)

【广度优先搜索】【二分图】【并集查找】2493. 将节点分成尽可能多的组
【二分图】【二分图最大匹配】LCP 04. 覆盖

割点、割边

很难点,割点周赛、双周赛没出过。 割边出现过一次。
割点原理及封装好的割点类 有四五题应用,不是必选算法

【图论】【 割边】【C++算法】1192. 查找集群内的关键连接

发表评论:

Powered By Z-BlogPHP 1.7.3

© 2018-2020 有趣的地方 粤ICP备18140861号-1 网站地图