poj 2421 Constructing Roads (kruskal) runtime error

链接：http://poj.org/problem?id=2421

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 210
#define maxm (210*210)

using namespace std;

struct node
{
	int u, v;
	int w;
}edge[maxm];
int n, m,Q;
int parent[maxn];

bool cmp(const node &a,const node &b)
{
	return a.w < b.w;
}

void UFset()
{
	for(int i = 0; i<= n; i++ )
		parent[i] = -1;
}

int Find( int x )
{
	int s;
	for( s = x; parent[s] >= 0; s = parent[s]);
	while( s != x)//此处优化，减小深度，可以节省大量的时间 
	{
		int temp = parent[x];
		parent[x] = s;
		x = temp;
	}
	return s;
}

void Union(int R1,int R2)
{
	int r1 = Find(R1);
	int r2 = Find(R2);
	int temp = parent[r1] + parent[r2];
	if(parent[r1] > parent[r2])//合并到绝对值值较大的，节省时间 
	{
		parent[r1] = r2;
		parent[r2] = temp;
	}
	else
	{
		parent[r2] = r1;
		parent[r1] = temp;
	}
}

void kruskal( )
{
	int u, v;
	int sumweight = 0;
	int num = 0;
	for(int i = 1; i < m; i++ )//注意是"<"m而不是 "<=",一直runtime error  就是因为这点错了 
	{
		u = edge[i].u;
		v = edge[i].v;
		if(Find(u) != Find(v) )
		{
		//	printf(" i = %d, u = %d, v = %d\n",i ,u, v);
			sumweight += edge[i].w;
			num++;
			Union( u,v );
		}
		if(num >= n-1 ) break;
	}
	printf("%d\n",sumweight);
}

int main()
{
	int w,u,v;
	while(scanf("%d",&n) != EOF)
	{
		int cnt = 1;
		for( int i = 1; i <= n; i++ )
		{
			for( int j = 1; j <= n; j++ )
			{
				scanf("%d",&w);
				edge[cnt].u = i;
				edge[cnt].v = j;
				edge[cnt].w = w;
				cnt++;
			} 
		}
		m = cnt;	
		UFset();
		scanf("%d",&Q);
		for( int i = 0; i < Q; i++ )
		{
			scanf("%d%d",&u,&v);
			if(Find(u) != Find(v)) 
				Union( u,v );
		}
	//	printf("m = %d\n",m);
		sort(edge, edge+m, cmp);
		kruskal( );
	}
	return 0;
}