expect2004

图论 - Ta...

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划(19) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 后缀数组（SA）(3) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

全部文章 / 图论 - Tarjan （共4篇）

LG2921 [USACO2008DEC]Trick or Treat on the Farm 内向基环树

问题描述 LG2921 题解发现一共有 \(n\) 个点，每个点只有一条出边，即只有 \(n\) 条边，于是就是一个内向基环树。 \(\mathrm{Tarjan}\) 缩点。但是这个题比较猥琐的就是有自环。所以断定一个强联通分量 \(i\) 是环的条件是 \(size_i&g...

2019-10-18

0 449

LG3119 「USACO2015JAN」Grass Cownoisseur

问题描述 LG3119 题解显然，如果有个环，一定是全部走完的。所以缩点，缩出一个 \(\mathrm{DAG}\) 。只能走一次反向，于是在正图和反图上各跑一次，枚举边，取 \(\mathrm{max}\) 即可。 \(\mathrm{Code}\) #include&...

2019-10-11

0 411

LG4819/BZOJ2438 「中山市选2011」杀人游戏 Tarjan缩点+概率

问题描述 LG4819 BZOJ2438 题解发现如果有一些人之间认识关系形成环，只需要问一个人就能把控整个环。 \(\mathrm{Tarjan}\)缩点。缩点之后所有入度为\(0\)的点，必须询问。注意特判有没有孤身一人的。 \(\mathrm{Code}\) #...

2019-09-10

0 507

LG2272/BZOJ1093 「ZJOI2007」最大半连通子图 Tarjan缩点+DAG求最长链

问题描述 LG2272 BZOJ1093 题解观察半联通的定义，发现图中的一些结点，构成的链一定是一个半联通子图。此时存在的环可能会干扰求解，于是\(\mathrm{Tarjan}\)缩点。于是求最长链，过程中计数即可。 \(\mathrm{Code}\) #inclu...

2019-09-09

0 573