SSuryxin

分类

ACM个人赛题解(2) CF(1) dp(2) 图论(12) 数论(1) 笔记(5) 题解(29)

/ 注册

TA的专栏 3篇文章 0人订阅

3篇文章 1160人学习

全部文章（共5篇）

Cow Ski Area

Cow Ski Area 题目描述：滑冰，给你一个地图，值代表高度，你只能从高到低滑，相同高度的点可以随便滑，除了根据势能来滑动，你还可以建造传送门，可以无视传送机起点到终点的高度随便走，即双向的，众所周知，传送门很贵，你现在想知道最少造几个传送门使得任意一个点都可以滑到全图所有点思路： ...

链式前向星缩点 tarjan dfs 拓扑排序

2021-08-13

1 537

[ZJOI2007]最大半连通子图

[ZJOI2007]最大半连通子图题目描述：给你一个图G，让你求最大半连通子图拥有的节点数K，以及不同的最大半联通子图的数量C，C要对X取模思路：这是一个比较复杂的题？主要思路是：tarjan缩点+拓扑排序+dp 首先使用tarjan缩点，得到一个有向无环图，缩点的时候需要记录每个点...

链式前向星缩点 tarjan 拓扑排序 dp

2021-08-13

1 610

[HAOI2006]受欢迎的牛

[HAOI2006]受欢迎的牛题目描述：众所周知，喜欢是可以传递的（bushi，给你N头牛，给你M对喜欢关系，如果A喜欢B，B喜欢C，则我们认为A也喜欢C，现在需要求有多少头牛被所有牛喜欢思路：还是先进行tarjan缩点，当且仅当存在一个出度为0的点集，则输出该点集的数量，否则输出0 ...

链式前向星缩点 tarjan 拓扑排序

2021-08-13

1 497

可达性

可达性题目描述：给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图，输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。 u1s1，这个题目描述讲的很难懂，你说是阅读理解都不为过，特别是最后一句，什么叫...

tarjan 缩点链式前向星拓扑排序

2021-08-13

0 764

拓扑排序详解（梅开二度之dfs版判环 + dfs版按字典序输出拓扑路径 + dfs版输出全部拓扑路径

什么是拓扑排序？先穿袜子再穿鞋，先当孙子再当爷。这就是拓扑排序！拓扑排序说白了其实不太算是一种排序算法，但又像是一种排序（我是不是说了个废话qwq）他其实是一个有向无环图（DAG, Directed Acyclic Graph的所有顶点的线性序列，该序列需要满足两个条件：每个节点只能出现一...

dfs 拓扑排序图论字典序

2021-04-27

1 717