网站首页
编程语言
数据库
系统相关
其他分享
编程问答
回边
2024-10-24
暑假集训随笔
1.关于二分图的判断:除了黑白染色法,还可以用扩展域并查集。所谓扩展域并查集就是假设每个点可能在集合1中也可能在集合2中,就把点i拆成i和i+n,分别代表在1和在2中的i。如果i和j不在同一集合中,就把i与j+n,以及j与i+n放在同一集合中。这样的好处是无论通过i还是j都可以拿到与它们在同一