int FindSet(int x)   // 找集合
{
	while(P[x] != x)
		x = P[x];
	return x;
}

bool FindPath(int x, int tar)   // 找x到根的路径是否有tar, 说明tar是x的祖先,这个在后面用来找矛盾
{
	while(P[x] != x)
	{
		x = P[x];
		if(x == tar) return true;
	}
	return false;
}

void Link(int x, int y)   // 合并两个集合
{
	if(P[x] > P[y])
	{
		P[y] = P[x];
		rank[x] += rank[y];
	}
	else
	{
		if(P[x] != P[y])
			rank[y] += rank[x];
		P[x] = P[y];
	}
	return;
}

// 下面这个把右边集合合并到左边,并且预先检查右边的是否有可能是x的祖先(如果是,就冲突了)
bool LeftJoin(int x, int y) // join the right set to the left one, check if conflicts
{
	if(FindPath(x, y) == true)  // no need to do anything any more
		return false;
	Link(FindSet(x), FindSet(y));
	return true;
}

我加上了这个,但是wa了,青椒高手

• 并查集我不会 :( 请教 (732) fluke 2006-08-31 16:53:48
  • 本题不用并查集 直接用差分就可以了 另 (287) sasnzy 2006-09-01 08:38:10
    • 说错是 是没有压缩 不是没有合并 (329) sasnzy 2006-09-01 08:38:40