AcWing1250格子游戏（并查集）

题目地址：https://www.acwing.com/problem/content/1252/

题目描述

Alice和Bob玩了一个古老的游戏：首先画一个 n×nn×n 的点阵（下图 n=3n=3 ）。

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

直到围成一个封闭的圈（面积不必为 11）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！

他们甚至在游戏中都不知道谁赢得了游戏。

于是请你写一个程序，帮助他们计算他们是否结束了游戏？

输入格式

输入数据第一行为两个整数 nn 和 mm。nn表示点阵的大小，mm 表示一共画了 mm 条线。

以后 mm 行，每行首先有两个数字 (x,y)(x,y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 DD，则是向下连一条边，如果是 RR 就是向右连一条边。

输入数据不会有重复的边且保证正确。

输出格式

输出一行：在第几步的时候结束。

假如 mm 步之后也没有结束，则输出一行“draw”。

数据范围

1≤n≤2001≤n≤200，
1≤m≤24000

题解：第一眼看见这道题以为超级难，结果听大佬一讲发现就是一道裸的并查集。。。。。。

题目问你什么时候结束，那么结束的标志就是产生一个环，那么怎么判定是否产生了一个环。这就需要并查集直接操作就可以了，如果当前这条边的两端在同一个集合中，那么就是一个环。那么剩下的就只有一个小问题了，就是并查集一般是在一维空间下，这里就需要将二维空间转换为一维空间，x*n+y,只要x,y都是从0开始的就可以了。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=210;
const int M=24010;
int fa[N*M],n,m;
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
int main(){
    cin>>n>>m;
    int ans=0;
    char ch;
    for(int i=1;i<=n*m;i++) fa[i]=i;
    for(int i=1,x,y,a,b;i<=m;i++){
        cin>>x>>y>>ch;
        a=x*n+y;
        if(ch=='D') x++;
        else y++;
        b=x*n+y;
        int ra=find(a),rb=find(b);
        if(!ans&&ra==rb) {
            ans=i;
        }
        fa[ra]=rb;
    }
    if(ans) cout<<ans;
    else cout<<"draw";
    return 0;
} 

写于：2020/8/22 18:10