【BZOJ 4423】[AMPPZ2013] Bytehattan

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4423
神犇题解:http://medalplus.com/?p=2428

解题报告

这个算是套路题吧?
考虑对偶图,两点之间不联通
当且仅当,一个点周围的空白部分全部联通

于是我们转成对偶图之后,用并查集判一判连通性就好
具体来说:删除一条边之前,如果该边相邻的空白区域已经联通则删除该边后两端点不联通
否则不影响连通性