普通并查集

格子游戏

题目描述

参考题解

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 4e4+5;

int n, m;

int p[N];

int find(int x)
{
    if(x != p[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;
    int ans = 0;
    for(int step = 1; step <= m; ++ step)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x -= 1, y -= 1; 
        char op[2];
        scanf("%s", op);
        if(ans > 0) continue;
        int a, b;
        a = get(x, y);
        if(op[0] == ‘D‘)
        {
            b = get(x+1, y);
        }
        else
        {
            b = get(x, y+1);
        }
        a = find(a), b = find(b);
        if(a == b)
        {
            ans = step;
        }
        p[a] = b;
    }
    if(ans > 0)
    {
        printf("%d\n", ans);
    }
    else
    {
        cout << "draw" << endl;
    }
    return 0;
}

并查集

原文：https://www.cnblogs.com/chaosliang/p/14771658.html