题目链接：http://acm.upc.edu.cn/problem.php?id=2372

2372: 连通块(blocks)

Time Limit: 1 Sec   Memory Limit: 64 MB
Submit: 37   Solved: 5
[ Submit][ Status][ Web Board]

Description

Input

Output

Sample Input

3 5
1 1 1
1 1 2
0 2 2
1 3 1
1 2 1

Sample Output

1
1
2
3
2

HINT

我的想法是，二维并查集，把连成一片的棋子并在一起，下一次判断的时候只需要看是否存在同一个根，是则不需要加，不是则+。可是TLE了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <list>
#include <vector>
using namespace std;
struct node
{
	int x,y,c;
	bool operator ==(node a)
	{
		if (a.x==x && a.y==y) 	
			return 1;
		else return 0;
	}
}f[520][520],t[500*501];
int dir[4][2]={
   {-1,0},{0,1},{1,0},{0,-1}};
node find(int x,int y)
{
	if (x==f[x][y].x && y==f[x][y].y)
		return f[x][y];
	else return f[x][y]=find(f[x][y].x,f[x][y].y);
}
int main()
{
	int n,m,i,j,c,a,b;
	while (~scanf("%d%d",&n,&m))
	{
	/*	for (i=0;i<=n+1;i++)
			for (j=0;j<=n+1;j++)
			{
				f[i][j].x=i;
				f[i][j].y=j;
				f[i][j].c=2;
			}*/
		memset(f,-1,sizeof(f));
		int ans=0;
		for (i=1;i<=m;i++)
		{
			scanf("%d%d%d",&c,&a,&b);
			ans++;
			t[i].x=a;
			t[i].y=b;
			f[a][b].x=a;
			f[a][b].y=b;
			f[a][b].c=c;
			for (j=0;j<4;j++)
			{
				if (f[a+dir[j][0]][b+dir[j][1]].c==f[a][b].c)
				{
					node k1=find(a+dir[j][0],b+dir[j][1]);
					node k2=find(a,b);
					if (k1==k2) continue;
					else
					{
						ans--;
						f[k1.x][k1.y].x=k2.x;
						f[k1.x][k1.y].y=k2.y;
					}
				}
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

又提交了一发DFS搜索，还是TLE!!!这是要虐我千百遍吗？

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <list>
#include <vector>
using namespace std;
int xx[4]={-1,1,0,0};
int yy[4]={0,0,-1,1};
int vis[520][520],mp[520][520],n,m;
int check(int x,int y,int t)
{
	if (x<1 || x>n || y<1 || y>n || mp[x][y]!=t || vis[x][y]==1)
		return 0;
	return 1;
}
void DFS(int x,int y,int t)
{
	for (int i=0;i<4;i++)
	{
		int x1=x+xx[i];
		int y1=y+yy[i];
		if (check(x1,y1,t))
		{
			vis[x1][y1]=1;
			DFS(x1,y1,t);
		}
	}
}
int main()
{
	int i,a,c,b,j,k;
	while (~scanf("%d%d",&n,&m))
	{
		memset(mp,0,sizeof(mp));
		for (i=1;i<=m;i++)
		{
			scanf("%d%d%d",&c,&a,&b);
			if (c==1)
				mp[a][b]=1;
			if (c==0)
				mp[a][b]=2;
			memset(vis,0,sizeof(vis));
			int ans=0;
			for (j=1;j<=n;j++)
				for (k=1;k<=n;k++)
				if (vis[j][k]==0 && mp[j][k]!=0)
				{
					ans++;
					vis[j][k]=1;
					DFS(j,k,mp[j][k]);
				}
			cout<<ans<<endl;
		}
	}
	return 0;
}

终于知道为什么TLE了。因为不是用的printf而是cout.所以超时了！！！！啊！！！