已注销

tarjan算法

二分图(2) 未归档(22) 网络流(2) 读书笔记(4) 题解(11)

/ 注册

全部文章 / tarjan算法（共7篇）

算法记录-6-（tarjan-有向图连通性）

tarjan-强连通分量 #include<iostream> #include<cstring> #include<vector> using namespace std; const int N=100010,M=1000010; int ver[M],Nex...

2020-11-01

0 457

算法记录-4-（tarjan-无向图连通性）

tarjan--求一张无向图中所有的桥》》书上的样例 #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; cons...

2020-11-01

0 577

5-（tarjan-结合题目条件-寻找权值最小的桥）

https://vjudge.net/problem/HDU-4738#author=Dillydally思路： 1.注意重边处理。2.守卫为0时，也需要派一个人；3.如果原本图不连通，就不需要派人。4.然后直接输出桥的最小边权就可以了。相对简单，详情不再赘述 #include<iostrea...

2020-10-29

1 538

4-（tarjan-给定一个有向图，求最大可以增加多少条边使得这个仍然不是强连通）

https://vjudge.net/problem/HDU-4635#author=634579757有t组数据，给了一个n个点m条边的有向图，问给此图最多加多少条边，满足如下条件:1：此图不能强连通2：没有重边和自环3：当图本身就是强连通的时候就输出-1那么现在我们考虑，如何加边使得加的边尽可能...

2020-10-29

1 666

3-（tarjan-使图中任意2点之间至少存在2条不同的路径-应该添加的路径数目）

https://vjudge.net/problem/POJ-3177#author=haomie思路：本质上就是用求边双连通分量的思路来求解；首先我们可以对图进行边连通分量缩点，缩点后图就会变成一颗树，代表任意2点之间的路径是唯一的。这时候题目转化为添加最少的边使任意2点的路径至少有2条。结...

2020-10-28

1 525

2-（tarjan-DAG-最少从几个点出发能够走遍全图-最少加上几条边能够该图变为强连通图)

https://vjudge.net/problem/POJ-1236思路：一个DAG上从入度为0的点出发一定可以走遍当前DAG, 所以第一问输出入度为0的点的个数对于一个DAG, 入度为0的一定是起点, 出度为0的一定是终点. 仔细思考一下, 如果只有一个起点显然应该加一条边, 如果只有一个终点...

2020-10-28

1 642

1-（tarjan-求联通块个数-分别列举去掉每个点的情况）

https://ac.nowcoder.com/acm/contest/7501/D思路：用Tarjan算法的思路来写，dfn[i]代表结点 i 的dfs序，low[i]代表从结点 i dfs下去能到达的dfn值最小的结点的dfn值。若x为当前结点，y为一个x的未被访问过的子节点，若对 y dfs完...

2020-10-28

1 667