题解：P10665 [AMPPZ2013] Bytehattan

· · 题解

蒟蒻看不懂题解区的话啊。

可以看作多个环由多个边从中心点向外延展。

当断掉环时，就在这个环的外环和内环寻找是否存在连通路径，这很简单，但是考虑到这条路径可能有多个内环或外环组成所以要想并查集里想。

强制在线的情况下，再像离线处理并查集那样显然是不太现实的，那么我们通过惊人的注意力注意到只要存在这条可达路径，再删掉这条边之前与边相邻的两个块是不连通的，举个栗子：

这个图有点不美观和不合理，但这只是个栗子，可以发现可达路径会和被删除的边构成环将里外两个块分开。

得出结论：如果在删边之前两个块不连通就说明存在可达路径，反之不存在。可以这么简单的推导那这题为啥还有紫。

:::info[如何处理删除最外面的环边？] 很简单，我们可以假想外面有一个环与原来最外面的环不连通，且与原来最外面的环构成一整个块。 :::

:::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1510;
int n,m,id[N][N],fa[N*N],tot;

static inline int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}

static inline bool merge(int x,int y){
    x=find(x),y=find(y);
    if(fa[x]==fa[y])return 0;
    fa[x]=fa[y];
    return 1;
}

signed main(){
    cin.tie(),cout.tie();

    cin>>n>>m;

    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            id[i][j]=++tot;
            fa[tot]=tot;
        }
    }

    bool flag=true;

    while(m--){
        int a[3],b[3];
        char c[3];
        cin>>a[0]>>b[0]>>c[0]>>a[1]>>b[1]>>c[1];
        if(flag)a[2]=a[0],b[2]=b[0],c[2]=c[0];
        else a[2]=a[1],b[2]=b[1],c[2]=c[1];

        int idx[2];

        if(c[2]=='N')idx[0]=id[a[2]][b[2]],idx[1]=id[a[2]-1][b[2]];
        else idx[0]=id[a[2]][b[2]],idx[1]=id[a[2]][b[2]-1];

        flag=merge(idx[0],idx[1]);

        if(flag)puts("TAK");
        else puts("NIE");
    }

    return 0;
}

:::