相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4423
神犇题解:http://medalplus.com/?p=2428
解题报告
这个算是套路题吧?
考虑对偶图,两点之间不联通
当且仅当,一个点周围的空白部分全部联通
于是我们转成对偶图之后,用并查集判一判连通性就好
具体来说:删除一条边之前,如果该边相邻的空白区域已经联通则删除该边后两端点不联通
否则不影响连通性
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4423
神犇题解:http://medalplus.com/?p=2428
这个算是套路题吧?
考虑对偶图,两点之间不联通
当且仅当,一个点周围的空白部分全部联通
于是我们转成对偶图之后,用并查集判一判连通性就好
具体来说:删除一条边之前,如果该边相邻的空白区域已经联通则删除该边后两端点不联通
否则不影响连通性