并查集-格子游戏

题目描述
Alice和Bob玩了一个古老的游戏：首先画一个n*n的点阵（下图中n=3），接着他们两个轮流在相邻的点之间画上虚边和粗边：
直到围成一个封闭的圈（面积不必为1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了（n<=200），他们的游戏实在是长了！他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序，帮助他们计算他们是否结束了游戏？
输入
每组输入数据第一行为两个整数n和m。m表示一共画了m条线。以后m行，每行首先有两个数字（x,y），代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是“D”，则是向下连一条边，如果是“R”就是向右连一条边。输入数据不会有重复的边且保证正确。

输出
对于每组数据，输出一行：在第几步的时候结束。假如m步之后也没有结束，则输出一行“draw”。

样例输入

3 5
1 1 D
1 1 R
1 2 D
2 1 R 
2 2 D

样例输出

4

算法思想
	直接用并查集 ，如果一条线的两个点指向的父节点都相同  那就表示围成了
	一个封闭的圈

#include
#include
#include

using namespace std;

const int N = 5e4 + 10;

int group[N];	// 存储该点的父亲点的位置 

int n,m;

// 并查集 find 
int find(int x){
	if(group[x] != x) group[x] = find(group[x]);
	return group[x];
}

int main(){
	
	cin >> n >> m;
	// 初始化每个点都是一个集合 
	for(int i = 1; i <= n*n;i++){
		group[i] = i;
	}
	
	for(int i = 1; i <= m;i++){
		int x,y;
		char flag;
		cin >> x >> y >> flag;
		// 如果不-1 group 将会少最前面一行 初始化 最后一行也会缺失 
		int f = (x-1) * n + y;
		// f+n 下一行的这个点 
		if(find(f) == find(f + n) && flag == 'D'){
			cout << i << endl;
			return 0;
		//	下一列的这个点 
		}else if(find(f) == find(f + 1) && flag == 'R'){
			cout << i << endl;
			return 0;
		}
		
		//	将这个点加入到集合中 
		if(flag == 'D'){
			group[find(f+n)] = find(f); 
		}else if(flag == 'R'){
			group[find(f+1)] = find(f);
		}
	}
	cout << "draw" << endl;
	return 0;
}