【Acwing】并查集 1250. 格子游戏

Love The Way You Lie 2024-04-01 18:20 89阅读 0赞

[1250. 格子游戏 - AcWing题库][1250. _ - AcWing]

题意：

![0938fadbad7342ac877b3c6a40774b19.png][]

思路：

当形成环的时候结束游戏，那么什么时候形成环呢？当一个点重复被塞进一个集合的时候就是形成环的时候。

那么我们怎么知道什么时候出现环了呢，典中典之并查集判环即可

在使用并查集时，首先需要建图（这一点和图论一样，其实并查集在某种层面也算是图论）

在建图的时候，我们先确定什么是结点，然后再确定什么是边，这样会清晰很多

在这道题中，结点就是格点，边就是图中的边

我们如何表示一个唯一的格点：按坐标哈希一下即可

建完图后，做一遍并查集就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=4e4+10;
    int n,m,x,y,a,b;
    int f[mxn];
    string op;
    int find(int x){
        return f[x]=(x==f[x]?x:find(f[x]));
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>n>>m;
        for(int i=1;i<=n*n;i++) f[i]=i;
        for(int i=1;i<=m;i++){
            cin>>x>>y>>op;
            a=(x-1)*n+y;
            if(op=="D") b=x*n+y;
            else b=(x-1)*n+y+1;
            if(find(a)==find(b)){
                cout<<i<<'\n';
                return 0;
            }else{
                join(a,b);
            }
        }
        cout<<"draw"<<'\n';
    }

**总结：**

**1.判环可以使用并查集**

**2.使用并查集之前，先建图（确定什么是结点，什么是边），再去套并查集**

[1250. _ - AcWing]: https://www.acwing.com/problem/content/1252/
[0938fadbad7342ac877b3c6a40774b19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4a5188b53d924d7a9cb64cc2629401d6.png