题目传送门：bzoj4423
如果是普通的删边判连通性，我们可以很显然的想到把操作离线下来，倒着加边。然而，这题强 制 在 线。
虽然如此，但是题目所给的图是个平面图。那么我们把它转成对偶图试试看？
在对偶图上，删边变成了加边（把边两边的网格连通起来）。并且，我们可以发现，如果在对偶图上加边时发现出现了一个环，那么就说明这个环中间的格点被完全同外面的格点切断了联系（包括刚才删去的边两侧的点）。
于是我们就只需在对偶图上用并查集维护对偶图的连通性即可。
代码：
#include<cstdio>
#define maxn 1510
using namespace std;
int fa[maxn*maxn];
int n,m,lastans;
inline int getid(int x,int y)
{
if(x<||y<||x>=n||y>=n)return ;
else return (x-)*n+y;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void work(int x,int y,char op)
{
int f1,f2;
if(op=='N')f1=find(getid(x-,y)),f2=find(getid(x,y));
else f1=find(getid(x,y-)),f2=find(getid(x,y));
if(f1==f2)printf("NIE\n"),lastans=;
else fa[f1]=f2,printf("TAK\n"),lastans=;
}
int main()
{
scanf("%d%d",&n,&m);
lastans=;
for(int i=;i<=n*n;i++)fa[i]=i;
for(int i=;i<=m;i++){
int x1,y1,x2,y2;
char c1,c2;
scanf("%d %d %c %d %d %c",&x1,&y1,&c1,&x2,&y2,&c2);
if(lastans)work(x1,y1,c1);
else work(x2,y2,c2);
}
}
bzoj4423