ACM算法

读文章代码

读文章代码
#include <bits/stdc++.h> using namespace std; int main() { ofstream file; file.open("yuyin.txt"); string s; cha...

ACM算法

tarjan之双连通图(无向图)

tarjan之双连通图(无向图)
这里有几个点需要注意 1.为什么无向图缩点需要变成有向图缩点? 无向图两两之间的点可以到达,无法跑回边的话,就跑不到父节点以上的节点了,那么肯定是桥了。 2.为什么不能跑回边,而不是跑父节点? 本来是个无向图单连通,但是你阻止了父节点跑回去,那就不是无向图单连通了。 但是这个题去...

ACM算法

tarjan算法之桥

tarjan算法之桥
博客推荐 与割点的最大不同之处:low[v]>low[u] 易错点: 1.父亲节点与子节点区别一下,防止两个点误认为环。 2.去重边 #include<stdio.h> #include<string.h> #include<string&...

ACM算法

tarjan算法之无向图求割点

tarjan算法之无向图求割点
先学tarjan算法,再学割点,优质博客 . 割点也就是把此点去掉后,使无向强连通图至少变成2部分。 1.哪些点是割点? 2.此割点把图割成了几部分? 第一个问题:1.如果根有两个或两个以上的树,那么此点必为割点。 2.如果u不是根节点,它有一个子节点v,并且以v为根节点的子树中...

ACM算法

tarjan算法之有向图缩点

tarjan算法之有向图缩点
1.求至少选几个点作为起点走遍全图(也就是这几个点走的路加起来走遍全图)? 2.求最小加多少边能使图变成强连通图? tarjan缩点求入度为0的点为第一个题的答案,求max(入度为0的点,出度为0的点)为第二个题的答案。 tarjan缩点方法最后给出代码。 疑问: 1.缩点之后的...

ACM算法

tarjan算法之有向图求连通分量

tarjan算法之有向图求连通分量
过程我就不多说了,百度一下,一堆博客。 我参照kuangbin的板子和hdu1269学的基础。 只会敲板子是非常不开心的,所以我自己想了想过程为什么这样写,以下纯属个人理解,如果有错,欢迎指出。 1.我就想为什么在一个连通内只有一个节点dfn[i]==low[i]? 借鉴此博客理...

world

2017年总结与2018展望

2017年总结与2018展望
总结: 应该是从大一下学期算吧! 1.经过两次开学,对比一下,发现惊人的相似。开学之前发誓要刻苦努力,但是一开学就开始无尽的玩耍(没有目标,不管是看动漫也好,看电影,看电视剧,都是脑子一热就开始了,然后有些就没有终点,像电视剧就没有终点,电影因为短,所以很快就看完了,动漫挑出了自...