并查集详解
https://blog.csdn.net/sjystone/article/details/115406797

格子游戏 https://www.acwing.com/problem/content/1252/

将格子的每个点抽象成图论中的点
出现圈的条件：当前连接的点（画的边的两个端点），已经在同一个连通块当中

把二维坐标转换为一维坐标（x和y都从0开始，二维数组大小是n*n）：
(x, y) -> x * n + y
如n = 3时
0 1 2 对应一维：0 1 2 3 4 5 6 7 8
3 4 5
6 7 8

若x从1开始 (x, y) -> (x - 1) * n + y
(x - 1) * n表示其该行的前边几行的的数字个数，再加上y即可得到

#include <iostream>
#include <cstring>
using namespace std;

const int N = 40010;
int f[N], p[N], n, m, res;

int find(int x) //找祖宗节点
{
    if ( p[x] != x ) p[x] = find(p[x]);
    return p[x];
}

int get(int x, int y)   //将二维数组转换为一维
{
    return x * n + y;
}

int main()
{
    cin >> n >> m;
    for ( int i = 0; i < N; i ++ ) p[i] = i;    //初始化每一个集合
    for ( int i = 1; i <= m; i ++ )
    {
        int x, y, a, b;     //x,y是当前坐标 a,b是对应一维数组的位置
        string op;
        cin >> x >> y >> op;
        x --, y --;         //下标从0开始
        a = get(x, y);
        if ( op == "D" ) b = get(x + 1, y);
        else b = get(x, y + 1);
        int pa = find(a), pb = find(b);
        if ( pa == pb )     //如果当前两个点在同一个集合中，游戏停止
        {
            res = i;
            break;
        }
        p[pa] = pb;         //如果当前两个点不在同一个集合，将他们放到同一个集合
    }
    if ( res != 0 ) cout << res << endl;
    else puts("draw");
    return 0;
}