【検索集】チェックゲーム

9132 ワード

データ構造

ソースリンク
そして裸問題を調べます.線で接続する2つの点が同じセット内にある場合、現在の操作は閉じられた輪に囲まれます.そうでないと、2点を同じセットに統合します.
コードの実装:

#include
#define N 1000000+10
using namespace std;

int n,m,ans=0;
int f[N];

int get(int x){
     
    if(f[x]==x)return x;
    return f[x]=get(f[x]);
}

void merge(int a,int b){
     
    f[get(a)]=get(b);
}

int main(){
     
    cin>>n>>m;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            f[i*n+j]=i*n+j;
            
    for(int i=1;i<=m;i++){
     
        int x,y;char ch;
        cin>>x>>y>>ch;
        
        if(ch=='D'){
     
            if(get(x*n+y)==get((x+1)*n+y)){
     ans=i;break;}
            merge(x*n+y,(x+1)*n+y);
        }
        
        if(ch=='R'){
     
            if(get(x*n+y)==get(x*n+y+1)){
     ans=i;break;}
            merge(x*n+y,x*n+y+1);
        }
    }
    
    if(ans==0)cout<<"draw";
    else cout<<ans;
    return 0;
}

図の構造の深さは優先的に遍歴され、広さは優先的に遍歴されている.