#include  <iostream>
#include  <algorithm>
#include  <math.h>
using  namespace  std;

int  n, m, k, num1, num2, sum;

int  i, j,  t;

int  used[104][104], parent[104][104], rank[104][104];

//建立一个节点 ，由于每个节点的位置都不同故可以用i*10+j来记录其位置
void  makeset(int  i, int  j)
{
	parent[i][j] = i*10 + j;
	used[i][j] = true;
	rank[i][j] = 1;

}

//寻找该点所在根节点，并压缩路径
int  findset(int  i, int  j)
{
	int  t;
	int  tempi =i, tempj = j;
	while( tempi*10 + tempj != parent[tempi][tempj] )
	{
		t = parent[tempi][tempj];
		tempi = t/10;
		tempj = t%10;
	}
	while( i*10 + j != tempi*10 + tempj)
	{
		t = parent[i][j];
		parent[i][j] = tempi*10 +tempj;
		i = t/10;
		j = t%10;
		
	}
	return  tempi*10 + tempj;
    
}

//合并两棵树，这里用rank[i][j]来记录根的地位并同时用其代表水坑的坑数

void unionset(int  i, int  j, int  i1,int  j1 )
{
	int  t = findset(i, j);
	int tep;//暂时变量
	i = t/10; j = t%10;
	t = findset(i1, j1);
	i1 = t/10; j1 = t%10;
	if( i == i1&& j == j1)
		return ;
	if( rank[i][j]>rank[i1][j1] )
	{
		parent[i1][j1] = parent[i][j];
		rank[i][j] += rank[i1][j1];
		tep = rank[i][j];
		
	}
	else
	{
		parent[i][j] = parent[i1][j1];
		rank[i1][j1] += rank[i][j];
		tep = rank[i1][j1];
	}
	if( tep > sum)
		sum = tep;
	

}



int  main()
{
	while (cin>>n>>m>>k)
	{
		memset(used , 0, sizeof(used));
		sum = 1;
		for( i = 0; i < 101; i++)
			for(j = 0; j < 101; j++)
				rank[i][j] = 1; 

		for( i = 1; i <= k ; i++)
		{
			cin>>num1>>num2;
			if(used[num1][num2])//如果坑已经输入了，就continue;
				continue;
			makeset(num1, num2);
			if(used[num1-1][num2])//以下四个用于找该点4周的树，若有，合并
				unionset(num1-1 , num2, num1, num2);
			if(used[num1+1][num2])
				unionset(num1+1, num2, num1, num2);
			if(used[num1][num2-1])
                 unionset(num1,num2-1, num1, num2);
			if(used[num1][num2+1])
				unionset(num1, num2+1, num1, num2);

		}
		cout<<sum<<endl;

	}
	return  0;
}

• Re:哪位能提供些测试数据啊，我用并查集做的，交上去老是WA，代码如下：如发现问题请指正 (2136) fireliuyu 2008-10-30 22:34:29
  • Re:哪位能提供些测试数据啊，我用并查集做的，交上去老是WA，代码如下：如发现问题请指正 (49) fireliuyu 2008-10-30 22:36:50
    • Re:哪位能提供些测试数据啊，我用并查集做的，交上去老是WA，代码如下：如发现问题请指正 (53) fireliuyu 2008-11-01 10:28:40
      • Re:哪位能提供些测试数据啊，我用并查集做的，交上去老是WA，代码如下：如发现问题请指正 (12) fireliuyu 2008-11-01 10:29:17