[文章目录]
Description
比特哈顿镇有n*n个格点，形成了一个网格图。一开始整张图是完整的。
有k次操作，每次会删掉图中的一条边(u,v)，你需要回答在删除这条边之后u和v是否仍然连通。n<=1500
每次删边后的询问都是对于当前边的两端点的。考虑对偶图，如果边的两边的块已经联通，那么断当前边会使两点不可达。
并查集维护对偶图连通性即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,fa[1600*1600];
inline int id(int i,int j)
{
if(j==0||j==n||i==0||i==n) return 0;
return (i-1)*(n-1)+j;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n*n;++i) fa[i]=i;
int ans=1,x,y,dx,dy; char sw[10];
while(m--)
{
if(ans) scanf("%d%d%s%*d%*d%*s",&x,&y,sw);
else scanf("%*d%*d%*s%d%d%s",&x,&y,sw);
if(sw[0]=='N') dx=id(x-1,y),dy=id(x,y);
else dx=id(x,y-1),dy=id(x,y);
if(find(dx)==find(dy)) ans=0,puts("NIE");
else fa[fa[dx]]=fa[dy],ans=1,puts("TAK");
}
return 0;
}