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判断连通性。

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz