【刷题】数据结构——并查集：格子游戏

【刷题】数据结构——并查集：格子游戏

题目是寻找第一次成环的时刻。

可以用并查集来维护各个点，如果两点间有边，则两点属于一个集合。只要看加上这条边之前两点是否在一个集合，即可判断成环的时刻。

因为n只有200，假设坐标编号是0~199，因此用 200 ∗ x + y 200*x + y 200∗x+y就可以不重复的表示所有坐标。
换而言之，假设坐标编号是0~n-1，用 n ∗ x + y n*x+y n∗x+y

当 ( x , y ) (x, y) (x,y)向下连线时， ( x , y ) (x, y) (x,y)与 ( x + 1 , y ) (x+1, y) (x+1,y)进行合并
当 ( x , y ) (x, y) (x,y)向右连线时， ( x , y ) (x, y) (x,y)与 ( x , y + 1 ) (x, y+1) (x,y+1)进行合并
合并前需判断两点是否已经在一个集合，如果在则直接输出当前步数。

#include 
using namespace std;

const int N = 40005;

int n, m;
int p[N], idx;

int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int main() {
	scanf("%d%d", &n, &m);
	int a, b, x, y;
	char op[2];

	for (int i = 0 ; i <= n * (n - 1) + n - 1; i ++ ) {
		p[i] = i;
	}
	
	for (int i = 1; i <= m; i ++ ) {
		scanf("%d%d%s", &x, &y, op);
		x -- ; y -- ; // 坐标从1~n换成0~n-1 
		a = n * x + y;
		if (op[0] == 'D') b = n * (x + 1) + y;
		else b = n * x + y + 1;
		if (find(a) == find(b)) {
			printf("%dn", i);
			return 0;
		}
		p[find(a)] = find(b);
	}
	printf("drawn");
	return 0;
}