树边,前向边,后向边,横叉边

转载自: 原文链接

树边,前向边,后向边,横叉边,应该说,不是一个图本身有的概念,应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树(森林),在这个树上才有了这些概念。对图进行DFS,可以从任意的顶点开始,遍历的方式也是多样的,所以不同的遍历会得到不同的DFS树,进而产生不同的树边,前向边,后向边,横叉边。所以这4种边,是一个相对的概念。
在图的遍历中,往往设置了一个标记数组vis的bool值来记录顶点是否被访问过。但有些时候需要改变vis值的意义。令vis具有3种值并表示3种不同含义
vis = 0,表示该顶点没没有被访问
vis = 1,表示该顶点已经被访问,但其子孙后代还没被访问完,也就没从该点返回
vis = 2,,表示该顶点已经被访问,其子孙后代也已经访问完,也已经从该顶点返回
可以vis的3种值表示的是一种顺序关系和时间关系

《算法导论》334页有这4种边的准确定义,在此不累述
DFS过程中,对于一条边u->v
vis[v] = 0,说明v还没被访问,v是首次被发现,u->v是一条树边
vis[v] = 1,说明v已经被访问,但其子孙后代还没有被访问完(正在访问中),而u又指向v?说明u就是v的子孙后代,u->v是一条后向边,因此后向边又称返祖边
vis[v] = 3,z说明v已经被访问,其子孙后代也已经全部访问完,u->v这条边可能是一条横叉边,或者前向边

注意:树边,后向边,前向边,都有祖先,后裔的关系,但横叉边没有,u->v为横叉边,说明在这棵DFS树中,它们不是祖先后裔的关系它们可能是兄弟关系,堂兄弟关系,甚至更远的关系,如果是dfs森林的话,u和v甚至可以在不同的树上

在很多算法中,后向边都是有作用的,但是前向边和横叉边的作用往往被淡化,其实它们没有太大作用。

bc #74 div1 1001 || hdu 5636 Shortest Path (floyd?)

题目链接
题意:有一条n个节点的链,节点i和节点j的距离为abs(i-j)
现在新增加三条边,距离也都为1,然后给出m个询问,每组询问给出两个点s,t,问s,t之间的最短距离。
思路:比赛的时候没搞出来。 观察特点,对于大多数点来说,都是没有直接的改变,只是增加了三条边。总的思路是:之前s到t的距离为abs(s-t),通过枚举中间经过的特殊点,观察是否能使得距离减小。

 

bc #77 ||hdu 5652 India and China Origins (图的动态连通性问题,并查集or 二分+bfs验证连通性)

题目链接
题意:没图不好描述,有中文题面中文题面,直接看吧。
思路:据说这道题有三种做法。 当时比赛一种都不会。

先说一种:做法是把格子看成点,可以到达的相邻格子之间看成有边相连,然后倒过来用并查集判断无向图的连通性。具体做法是:先统计初始所有空的位置,然后把所有要增加的山都加上(先统计空的位置是因为山之后要去掉,而去掉以后要得到该点的标号),然后将把所有空的点以及china(设标号为n*m+1)点,和india(设标号为n*m+2) 点通过并查集来合并..可以从上往下从左往右,每次只需要判断上面的点和左边的点是否有空,如果有就用并查集合并。 china点和india点特殊搞就好。

然后判断india和china是否联通,如果是则输出-1.否则从最后添加的山开始移除,每次移除一座山,添加四个方向能添加的边(注意这里不要忘记如果改点在第0行或者第n-1行还要添加和china或者india的边)

然后移除后询问india和china是否联通 (root(china)==root(india)?)

如果时间i联通了,而i+1没有联通,说明时间i是两国最早的失去联系的时间。

 

第一次做这种题目,这种题目的一般做法都是倒过来做。貌似还有一个二分删除的山+bfs判断连通性的。。。? 窝再搞搞看。
update :二分+bfs判断连通性。其实这个思路更常规。。做法就是字面意思。注意无解的判断即可。

 

并查集解法:

 

 

二分+bfs判断连通性。

bc #73 B || hdu 5631 Rikka with Graph (并查集判断无向图的连通性)

http://acm.hdu.edu.cn/showproblem.php?pid=5631
题意;给出一张n个点n+1(n<=100)条边的无向图,现在删除若干条边(至少一条边),问删完之后图依然联通的方案数。
思路:分析可知,由于只删边,不删点,n个点,最少需要n-1条边才能联通,所以最多删两条边。我们可以暴力枚举删除的两条边(或者一条边) O(n^2)的复杂度完全可以接受。剩下的问题就变成了每次删边之后判断图的连通性。 题解给出的是bfs。。。大概是bfs一遍,然后入队的点数是n就联通? 或者dfs一遍也可以? 也是标记过的点数是n就说明联通? 但是看到排名考前的人都是用到了并查集来判断…比较巧妙。

具体做法是:先把所有的点孤立出来,然后开始添加边,每次union成功(就是添加了一条边)的时候计数器+1,n个点如果能合并n-1次,也就是添加了n-1条有效边(最多也只可能是n-1条,那么说明这n个点之间是联通的。

第一次这样用并查集…憋说话,用心感悟。

 

 

hdoj 5606 ||bc #68 div 2 B tree

http://acm.hdu.edu.cn/showproblem.php?pid=5606
题意:一棵树,边权为0或者1,问对于每个点,距离它最近的点(包括自身)的个数是多少。输出将所有点的答案异或后的值。
思路:由于包括自身,自己与自己距离为0,那么最近的点一定也距离为0,所以就是找对于每个点与它相连的边权为0 的点的个数。建图的时候可以不管边权为1的点。。因为这样的点不会对任何点的答案有贡献。正解貌似是冰茶几。。我就是dfs搞了下。。找到每一个联通快的点数。。然后把某个联通快的所有点的答案都更新成点的个数。。。

 

 

codeforces 22 C. System Administrator

http://codeforces.com/contest/22/problem/C
题意:要求用n个点m条边构造一个不允许有重边的图,满足当去掉点v的时候,剩下的n-1个不联通。如果有答案输出任意,没答案输出-1.
思路:首先如果n个点要联通。。至少有n-1条边,此时为一棵树。但是是不是边越多越好呢?显然是不可以的。满足去掉一个点使得n-1个点不联通的情况为,存在一个点u只和v相连,不和任意任何其他点相连,那么当去掉v点,u点就变成不可到达了。边数最多的情况就是,除了v点以外的n-1个点,每个点的度都是n-2(去掉自身以及u点还有n-2个点),,那么除去u点以外的n-1个点的度数就是(n-1)*(n-2),边数则为(n-1)*(n-2)/2,再加一条连接u的边,所以图的最大边数为(n-1)*(n-2)/2+1,最小为n-1.

如果有解,那么接下来的问题是构造。

我是按照如下方式构造的:

先构造一条链,将u点放在第一个,v点放在第二个。不妨当v=1时令u=2,否则u=1;

m-=n-1,如果m还有剩余,那么从第二个点开始,一直到第n-2个点,每个点与至少隔1个点的其他点相连,直到边数没有剩余。

 

 

codeforces #333 div 2 C. The Two Routes

http://codeforces.com/problemset/problem/602/C
题意:给出n个城镇,m条双向铁路,对于任意不同的x,y,如果x,y之间没有铁路,那么一定有双向公路。train只能走铁路,bus只能走公路。现在一辆火车和一辆bus同时从1出发,要到达n,处于安全考虑,bus和火车不能同时处在除了n以外的点。bus和train不要求同时到达。任意一段道路的时间花费都是1小时。问最少需要多久使得bus和train都到达n。如果存在某个不能到达,那么输出-1.
思路:n才400.一开始打算先按照rail和road建两个图。这两个图互为补。然后在floyd的时候加以判断。但是马上就发现。。不能同时到达同伙一个点这个条件其实不会影响。。因为按照题意,一定存在一条1到n的路,不是公路就是铁路。那么就让有路的花费1的代价到n,然后剩下的求一个一到n的最短路即可。由于n才400.。最短路怎么搞都行。。我偷懒就用floyd了。

poj 3687 Labeling Balls

http://poj.org/problem?id=3687
题意:给定几个标签球的重量大小关系,求每个球是第几重的(即每个球在所有球的重量中由小到大排名是多少)。
输出是每个球第几重,而不是几号球比几号球重!)。一开始理解错了QAQ
思路:反向拓扑+优先队列。因为正向不好用。。。所以我们连边的时候由重的指向轻的。。这样最先出队的就是最重的。。和上道题差不多?

 

poj 3660 Cow Contest (floyd,传递闭包)

http://poj.org/problem?id=3660
题意:给定n个奶牛,m个奶牛的关系,a,b表示a比b强…问能确定多少个奶牛的排名。
思路:最重要的一点是。。能确定奶牛i的排名的条件是。。知道奶牛i和其他n-1个奶牛的关系。。不管是能打败奶牛i也好。。会被奶牛i打败也好。。只要不是不确定就行。。所以我们跑一遍floyd做传递闭包。得到任何两个点之间的联系。然后对于每一个点。看其他n-1个点是否和他有关系。

 

 

hdu 2647 rewards

http://acm.hdu.edu.cn/showproblem.php?pid=2647
题意:老板要给很多员工发奖金, 但是部分员工有个虚伪心态, 认为自己的奖金必须比某些人高才心理平衡; 但是老板很人道, 想满足所有人的要求, 并且很吝啬,想画的钱最少
输入若干个关系
a b
a c
c b
意味着a 的工资必须比b的工资高 同时a 的工资比c高; c的工资比b高

当出现环的时候输出-1

思路:因为点的个数比较多。。。用数组存点的关系存不下。。于是用set存边。。和用vector差不多。。。窝一开始的大思路错了。。以为会是一条链。。也就是没一个钱数只对应一个人。。。但实际上可以是889,888,888,这样。。。只要不矛盾。。然后要反向建图。。因为只知道最少的钱数是888,不知道最多的钱数是多少。。所以最先出来的,也就是入度为0的点应该为工资最少的。。。所以如果a应该比b工资高,那么连一条b指向a的边。

 

 

hdu 3342 Legal or Not

http://acm.hdu.edu.cn/showproblem.php?pid=3342
裸题。
注意有重边。

codeforces 574B Bear and Three Musketeers

http://codeforces.com/problemset/problem/574/B
题意:给定一个无相图。选出三个点,使得这三个点之间互相有边相连,且三个点的度数之和最小。
思路:暴力出奇迹。复杂度o(n2+n*m)

codeforces 510 C. Fox And Names

http://codeforces.com/contest/510/problem/C

题意:给定n个字符串。问是否存在一种字母顺序,使得这n个字符串的顺序满足字典序(自定义的)。如果有多种顺序,输出字典序(标准的)最小的。

思路:将字符串的关系处理成边的关系。每次对于第i个和第i+1个字符串,从前往后扫,直到不相等的那一位,设为k,然后连边,指向i+1。表明第i个字符串的第k位大于第i+1个字符串的第k位。如果没有不想等的。说明其中一个是另一个的字串。如果前者是后者的字串,那么不影响。如果后者是前者的字串,则不存在满足条件的字典序。然后做拓扑排序。由于有多种输出字典序(标准的)最小的方案。所以存点的时候用优先队列存。

 

hdu 2094 产生冠军

题意:给定n组u关系。每组表示a战胜b。。问根据这些关系能否确定冠军。
思路:如果a战胜b就从a连一条指向b的边。那么能确定冠军的条件就变成了,有且只有一个入度为0的点。翻译过来就是,有一个人没有被任何人战胜过。且,这样的人只有一个。一开始想用map来搞。。但是比较麻烦。。其实用set比较好。。开两个set,一个存所有的人,一个存输过的人。出度为0的点只有一个等价为,有且只有一个人没有输过。也就是两个set的元素差个数为1.

hdoj 1285 确定比赛名次

http://acm.hdu.edu.cn/showproblem.php?pid=1285
题意:

有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。
拓扑排序模板题。刷dfs的时候遇到的。干脆来学习下。
注意可能有重边。
由于要求输出顺序按照序号从小到达,所以这里用了优先队列。