我是这样压缩路径的但还是用了63ms,希望那些大牛不吝指教撒~
int FindParent(int x)
{
	if(parent[x] > 0) {
		parent[x] = FindParent(parent[x]);
		return parent[x];
	}
	else
		return x;
}
//把层次小的
void Union(int x,int y)
{
	x = FindParent(x);
	y = FindParent(y);
	if( x == y)
		return ;
	if(parent[x] < parent[y]) 
		parent[y] = x;
	else
		if(parent[x] > parent[y])
			parent[x] = y;
		else {
			parent[x]--;
			parent[y] = x;
		}
}

• 我的也63ms^_^ (821) nazgul1991 2010-04-06 16:07:28
  • 我的47ms,只用了路径压缩这一个优化 (1284) fyq 2010-05-08 22:02:24