Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3 ）。
接着，他们两个轮流在相邻的点之间画上红边和蓝边：
直到围成一个封闭的圈（面积不必为 11）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！
他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序，帮助他们计算他们是否结束了游戏？
输入格式
输入数据第一行为两个整数 nn 和 mm。nn表示点阵的大小，mm 表示一共画了 mm 条线。
以后 mm 行，每行首先有两个数字 (x,y)(x,y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 DD，则是向下连一条边，如果是 RR 就是向右连一条边。
输入数据不会有重复的边且保证正确。
输出格式
输出一行：在第几步的时候结束。
假如 mm 步之后也没有结束，则输出一行“draw”。
数据范围
1≤n≤2001≤n≤200，
1≤m≤240001≤m≤24000
输入样例：
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
输出样例：
4
一个特别有意思的并查集，在这里用map和pair来完成对坐标的存储。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<map> 5 using namespace std; 6 7 map<pair<int,int>,int> M; 8 9 const int N = 40010; 10 11 int p[N]; 12 13 int find(int x){ 14 if(x != p[x]) p[x] = find(p[x]); 15 return p[x]; 16 } 17 18 void _union(int x,int y){ 19 x = find(x); 20 y = find(y); 21 if(x != y) p[x] = y; 22 } 23 24 bool issame(int x, int y){ 25 return find(x) == find(y); 26 } 27 28 int n,m,t; 29 30 int main(){ 31 32 for(int i = 0; i < N; i ++) p[i] = i; 33 char s[4]; 34 cin >> n >> m; 35 36 int ans = -1; 37 38 for(int i = 0; i < m; i ++){ 39 int x,y,x1,y1; 40 cin >> x >> y >> s; 41 if(s[0] == 'D'){ 42 x1 = x+1; 43 y1= y; 44 }else{ 45 x1 = x; 46 y1= y+1; 47 } 48 if(!M.count({x,y})) M[{x,y}] = t ++; // 因为map中不存在相同的元素，所以count的返回值只能是1或者0,0代表还没有用到该点，1代表用到啦~ 49 if(!M.count({x1,y1})) M[{x1,y1}] = t ++; 50 if(issame(M[{x,y}],M[{x1,y1}])){ 51 if(ans == -1) ans = i + 1; 52 } 53 _union(M[{x,y}],M[{x1,y1}]); 54 } 55 if(ans == -1){ 56 printf("draw "); 57 }else{ 58 printf("%d ",ans); 59 } 60 return 0; 61 }