题目分类列表 当前分类: 连通性 (连通块 连通度 割顶 桥 块 连通图 无向图连通分量 有向图强连通分量 弱连通分量 Tarjan 利用dfs求出强连通分量来解决问题 深搜 用途广泛的Tarjan具有缩点、求SCC/DCC/LCA等诸多用途 经典的使用tarjan求强连通分量题目 看榜 可以缩点)
题目编号 题目名称 文件名称 时间 空间 难度 评测方式 通过 提交 通过率
3642 [HDOJ 3686]交通实时查询系统 图论 缩点 双连通分量 LCA 圆方树 连通分量 连通性 点双连通分量 traffic_query 1 s 256 MiB ★★★☆ 简单对比 3 12 25%
3143 [POI 2008]BLO-Blockade 双连通分量 连通性 割点与桥 BLO 1 s 128 MiB ★★★ 简单对比 19 45 42.22%
3045 [USACO Open18 Silver] Multiplayer Moo DFS 连通性 并查集 multimoo_silver_18open 1 s 256 MiB ★★ 简单对比 12 64 18.75%
2856 [洛谷3950]部落冲突 连通性 树链剖分 树上差分 lct 1 s 256 MiB ★★★☆ 简单对比 41 100 41%
2783 Alone 连通性 alone 1 s 256 MiB ★★★☆ 简单对比 6 26 23.08%
2552 [ZJOI 2008] 骑士 树形DP 连通性 基环树 基环树DP bzoj_1040 2 s 256 MiB ★★★ 简单对比 52 141 36.88%
2526 __围栏问题 连通性 搜索法 xfence 3 s 128 MiB ★★★ 简单对比 24 60 40%
2449 [APIO2009] 抢掠计划 连通性 最短路 动态规划 图论 DAG atm 1 s 64 MiB ★★★ 简单对比 80 152 52.63%
2415 [HZOI 2016]非触 树链剖分 HZOI 连通性 cp 2 s 256 MiB ★★★ 简单对比 40 149 26.85%
2408 [SCOI 2007]排列 状压DP 连通性 wulipailie 1 s 256 MiB ★★ 简单对比 89 133 66.92%
2257 [SHOI 2008]堵塞的交通traffic 线段树 连通性 bzoj_1018 1 s 162 MiB ★★★☆ 简单对比 44 175 25.14%
2106 [NOIP 2015]斗地主 连通性 动态规划 模拟 NOIP/CSP 估价函数 landlords 2 s 1025 MiB ★★★ 简单对比 250 971 25.75%
2105 [NOIP 2015]信息传递 搜索法 图论 NOIP/CSP 连通性 2015message 1 s 256 MiB ★★ 简单对比 466 1656 28.14%
1968 [HEOI 2015] 兔子与樱花 贪心 连通性 sakura 4 s 256 MiB ★★★ 简单对比 125 249 50.2%
1807 [NOIP 2014]寻找道路 最短路 NOIP/CSP 图论 搜索法 连通性 roadb 1 s 128 MiB ★★ 简单对比 379 1108 34.21%
1738 [HZOI 2014] 智哥的超时空传送 最短路 连通性 tramcar 1.2 s 64 MiB ★★☆ 简单对比 61 202 30.2%
1540 [Ural 1557] 网络攻击 图论 连通性 Ural networkattack 2 s 256 MiB ★★★ 简单对比 14 28 50%
1538 [AHOI 2005] LANE 航线规划 LCA RMQ 图论 树状数组 动态树 树链剖分 连通性 lane 1 s 64 MiB ★★★★ 简单对比 47 158 29.75%
1527 [UVa 11741] 网格覆盖 动态规划 状态压缩 矩阵运算 UVa 连通性 轮廓线DP ignoretheblocks 5 s 256 MiB ★★★ 简单对比 6 13 46.15%
1391 冲出亚马逊之圣战前夜 连通性 搜索法 种子填充 基本 ymxpre 1 s 256 MiB 简单对比 141 341 41.35%