关于扩展域并查集判断二分图的疑问
查看原帖
关于扩展域并查集判断二分图的疑问
65743
滑稽的小宫楼主2021/7/11 12:34

第一篇题解里面代码有这么一段:

int a = findfa(e[t[u].at(i)].x);
int b = findfa(e[t[u].at(i)].y);
if(a == b)
{
for(int k = l;k <= r;k++)
	printf("No\n");
	ans = 0;
	break;
}

我能理解如果x和y在一个集合内,显然增加这条边使x和y必须分到两边是不行的。但是我无法理解为啥不出现这种情况就一定是二分图?有没有可能连接x和y+n或者y和x+n以后把其他某个节点p和p+n合并到一个集合内了,就不是二分图了?

2021/7/11 12:34
加载中...