#570. 【例4-8】格子游戏

题题题题题题题题题题题题题题

分析：

• 并查集解决的是连通性（无向图连通分量）和传递性（家谱关系）问题，并且可以动态的维护。抛开格子不看，任意一个图中，增加一条边形成环当且仅当这条边连接的两点已经联通，于是可以将点分为若干个集合，每个集合对应图中的一个连通块。
• 此题的解题核心就是：两个已连通的点之间，再添加一条边就构成了一个环；，所以此题采用二维并查集来做，如果两个点已连通（祖先相同），那就满足题意，否则的话将这两个点之间建立联系（将这两个点连通起来）；
• 用了一个结构体node去存一个顶点的横坐标、纵坐标，f数组来存一个顶点的结构体信息（f[x][y]：存储（x,y）这个结点的横坐标、纵坐标）；在每次输入的一行操作，先判断当前的两点是否已连通，两个已连通的点之间，再添加一条边就构成了一个环；不连通，那就连起来

题解：

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct ji{
	int x,y;
}fu[210][210];//x,y坐标
ji find(ji k){//?
	if(fu[k.x][k.y].x==k.x  &&  fu[k.x][k.y].y==k.y)
		return fu[k.x][k.y];
	return fu[k.x][k.y]=find(fu[k.x][k.y]);
}
void merge(ji k1,ji k2){
	k1=find(k1);
	k2=find(k2);
	fu[k1.x][k1.y]=k2;
}
int main(){
	cin>>n>>m;
	int x,y;
	char c;
	for(int i=1;i<=n;++i){//初始化，每个坐标点为一个嘉足
		for(int j=1;j<=n;++j){
			fu[i][j].x=i;
			fu[i][j].y=j;
		}
	}
	ji k1,k2;
	for(int i=1;i<=m;++i){
		cin>>x>>y>>c;
		if(c=='D'){//连接(x,y)和(x+1,y)俩节点
			k1=find(fu[x][y]);
			k2=find(fu[x+1][y]);
		}
		else{//连接(x,y)和(x,y+1)俩节点
			k1=find(fu[x][y]);
			k2=find(fu[x][y+1]);
		}
		//判断当前两点是否已联通，两个已联通的点之间，再加一条边就构成了一个环
		if(k1.x==k2.x  &&  k1.y==k2.y){
			cout<<i;
			return 0;
		}
		else{//如果不连通就把他连起来
			merge(k1,k2);
		}
	}
	cout<<"draw";//跳出循环没有结果：输出draw
	return 0;
}