對酒當歌,人生幾何? 譬如朝露,去日苦多

tarjan算法之无向图求割点

先学tarjan算法,再学割点,优质博客 .割点也就是把此点去掉后,使无向强连通图至少变成2部分。1.哪些点是割点?2.此割点把图割成了几部分?第一个问题:1.如果根有两个或两个以上的树,那么此点必为割点。2.如果u不是根节点,它有一个子节点v,并且以v为根节点的子树中,没有一个顶点有通向任意一个u的祖先的回边。第二个问题:就是去点此割点,然后求并查集。#include<stdio.h> #include<string.h> #include<string> #include<iostream> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) #define LL long long using namespace std; const int maxn=200; int n,m; struct node { int v,nex; } e[maxn*maxn]; int first[maxn]; int tot,t...

tarjan算法之有向图缩点

1.求至少选几个点作为起点走遍全图(也就是这几个点走的路加起来走遍全图)?2.求最小加多少边能使图变成强连通图?tarjan缩点求入度为0的点为第一个题的答案,求max(入度为0的点,出度为0的点)为第二个题的答案。tarjan缩点方法最后给出代码。疑问:1.缩点之后的入度为0的点数量为什么为第一问的答案?入度为0,也就是没有点能够到达它,它也就是起点。但是入度不为0的点,总有点能够到达它。2.为什么max(入度为0的点,出度为0点)为第二问的答案?想让此图变成强连通图,就要消除起点和终点,那么就要取他们的最大值。 缩点最好用染的颜色缩点,由我前面的文章可知,一个连通分量的值不一定相等。然而有些题却能用low值过,嗯。。。。数据弱#include<stdio.h> #include<string.h> #include<string> #include<iostream> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) #defi...

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

过程我就不多说了,百度一下,一堆博客。我参照kuangbin的板子和hdu1269学的基础。只会敲板子是非常不开心的,所以我自己想了想过程为什么这样写,以下纯属个人理解,如果有错,欢迎指出。1.我就想为什么在一个连通内只有一个节点dfn[i]==low[i]?借鉴此博客理解答:由于位于同一个连通内,所以任意两个节点可以相互到达,那么两者的low值一定会被另一个所影响(要看谁的low最小),所以不可能存在两对dfn和low的值相等。但是一个连通图内的low值不一定都相等(例如3个点,6条边,1-2,2-1,2-3,3-2,3-4,4-3,自己去试试就知道了)。2.为什么low值要取最小的,最大的不可以吗?答:对于一个连通图,我们很容易想到,在该连通图中有且仅有一个节点u的DFN值和low值相等。该节点一定是在深度遍历的过程中,该节点为连通图中第一个被访问过的节点,因为它的dfn值和low值最小,不会被其他节点影响。最大的话,出栈那里就不对了。我们的一个连通图在栈中是根节点在最下面,也是最小的low,那么以这个为区分其他强连通分量具有重要意义,所以我们取最小。3.这个连通图内所有的点...

2017年总结与2018展望

总结:应该是从大一下学期算吧!1.经过两次开学,对比一下,发现惊人的相似。开学之前发誓要刻苦努力,但是一开学就开始无尽的玩耍(没有目标,不管是看动漫也好,看电影,看电视剧,都是脑子一热就开始了,然后有些就没有终点,像电视剧就没有终点,电影因为短,所以很快就看完了,动漫挑出了自己喜欢看的,最终也看完了,从中好像能吸取一点学习经验啊,对于喜欢的事物或不得不做的事物要坚持下去,不要冲动做事,好有道理)。主要经历了省赛选拔,大一期末考试,暑假集训,数学建模,和大二下学期的智障度过。2.省赛选拔真的很惨,因为自己太菜吧,还太要面子而感到伤心欲绝。3.大一下期末考试,想靠别人,结果监考太严,就凉了高数,任何事自己能做的绝对不要靠别人4.暑假集训,回宿舍之后没有好好学习,学习是孤独的,要加油!5.数学建模因为整个团队实力不够,实在没办法,对自己的认识应该是,该工作学习时,不要多bb。6.大二下学期刚开学一直不在状态,不知道为什么,我受其他人影响较大吧,别人不来,我也不来,然后我也没怎么学到东西,大二下学期比较惨吧!2018展望1.不要盲目跟风,有自己的计划。(比如:别人上课认真听课坐第一排,你...