> #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，代码如下：如发现问题请指正 (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