青竹qingzhu

tarjan

AC自动机(3) KMP(3) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

全部文章 / tarjan （共2篇）

hdu2767——tarjan强连通分量

hdu2767 题意给n个点和m条有向边，求最少还需多少条边n个点构成强联通图。思路 tarjan先处理出每一个强连通分量。如果强连通分量的个数为1，则答案为0。如果强连通分量的个数大于1，将每个强连通分量看成一个点，每个强连通分量之间可能存在边，a为没有出度的强连通分量的个数，b为没有入度...

2020-07-13

0 507

hdu4738——tarjan割边

hdu4738 题意 n个岛m座桥的无向图，每座桥上有若干个士兵，派出最少的士兵只炸毁一座桥，使得n个岛不连通（派出的士兵不能少于驻守的士兵，特别的改桥的驻守人数为0的时候要派一个士兵）。思路用tarjan算法，满足dfn[u] < low[v]的(u,v)就是割边，直接处理出来取最小值，...

2020-07-13

0 788