[BZOJ 4423][AMPPZ2013]Bytehattan（并查集+平面图转对偶图）

Description

比特哈顿镇有n*n个格点，形成了一个网格图。一开始整张图是完整的。
有k次操作，每次会删掉图中的一条边(u,v)，你需要回答在删除这条边之后u和v是否仍然连通。

Solution

很重要的是要想到这点…如果一条边隔开的两个空格在删边之前就已经联通，那么删边之后这条边的两个端点就不连通了

然后用并查集维护联通就好了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define MAXN 5000005
using namespace std;
int n,k,father[MAXN];
int pos(int x,int y)
{
    int p=(x-1)*(n-1)+y;
    if(x<=0||y<=0||x>n-1||y>n-1)return 0;
    return p;
}
int find(int x)
{
    if(x==father[x])return x;
    return father[x]=find(father[x]);
}
int main()
{
    scanf("%d%d",&n,&k);
    int last=1;
    for(int i=0;i<=(n-1)*(n-1);i++)father[i]=i;
    for(int i=1;i<=k;i++)
    {
        int a,b,c,d;
        char opt1,opt2;
        scanf("%d%d",&a,&b);
        opt1=getchar();
        while(opt1!='E'&&opt1!='N')opt1=getchar();
        scanf("%d%d",&c,&d);
        opt2=getchar();
        while(opt2!='E'&&opt2!='N')opt2=getchar();
        if(last)
        {
            if(opt1=='N')
            {
                int x=pos(a-1,b),y=pos(a,b);
                int fx=find(x),fy=find(y);
                if(fx==fy){printf("NIE
");last=0;}
                else {printf("TAK
");father[fx]=fy;last=1;}
            }
            else
            {
                int x=pos(a,b-1),y=pos(a,b);
                int fx=find(x),fy=find(y);
                if(fx==fy){printf("NIE
");last=0;}
                else {printf("TAK
");father[fx]=fy;last=1;}
            }
        }
        else
        {
            if(opt2=='N')
            {
                int x=pos(c-1,d),y=pos(c,d);
                int fx=find(x),fy=find(y);
                if(fx==fy){printf("NIE
");last=0;}
                else {printf("TAK
");father[fx]=fy;last=1;}
            }
            else
            {
                int x=pos(c,d-1),y=pos(c,d);
                int fx=find(x),fy=find(y);
                if(fx==fy){printf("NIE
");last=0;}
                else {printf("TAK
");father[fx]=fy;last=1;}
            }
        }
    }
    return 0;
}