题解：P10665 [AMPPZ2013] Bytehattan

· · 题解

咦为啥我啥都不会。加学。

网格是平面图，删边相当于在对偶图上加边。

如果对偶图上加这条边以前两个点已经连通，加边后两个点一定会被完全切断，于是不连通。

所以我们只需要维护一个只加边的对偶图的连通性就好了。

dsu 即可。

#include<bits/stdc++.h>
#define int long long
#define N (1501*1501)
using namespace std;
int n;
int id(int x,int y){
    return (x-1)*(n+1)+y;
}
int fa[N+5];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool solve(int u,int v,char c){
    int x=id(u+1,v+1);
    int y;
    if(c=='N')y=id(u,v+1);
    if(c=='E')y=id(u+1,v);
    if(find(x)==find(y))return 0;
    fa[find(x)]=find(y);
    return 1;
}
signed main(){
    int k;
    cin>>n>>k;
    for(int i=2;i<=n;i++)
    for(int j=2;j<=n;j++)
    fa[id(i,j)]=id(i,j);
    bool ans=1;
    while(k--){
        if(ans){
            int u,v;
            char c;
            cin>>u>>v>>c;
            ans=solve(u,v,c);
            cin>>u>>v>>c;
        }else{
            int u,v;
            char c;
            cin>>u>>v>>c;
            cin>>u>>v>>c;
            ans=solve(u,v,c);
        }
        if(ans)cout<<"TAK\n";
        else cout<<"NIE\n";
    }
    return 0;
}
// 并不是以战士的身份，当然更不是以勇者或英雄的身份。
// 他仅以一名诡辩家的身份参战，然后获得了胜利。