[二分图][棋盘][连通分量] codeforces Chemical table 1013D

http://codeforces.com/contest/1013/problem/D

题意：每次可以从矩形的3个角产生第4个角，问至少需要添加多少个方块可以使得让整张图都充满方块。

自己想的是奇怪的思路，因为发现一个联通的块可以扩展到这个块的maxx，maxy，但是之后就不知道怎么做了。看了题解才恍然大悟，原来是把坐标转化成二分图的左右节点，然后考虑连通分量的个数就可以了。证明的时候，首先注意到一点就是二分图中两个点之间的路径个数一定是奇数，对于同一个连通分量中的左右两个点x，y，他们之间的距离如果是1的话那说明二者之间一定有了一条路径了，也就是这个点已经有一个方块了，如果不是1那么至少是3，每次取距离y最近的3个点，按照题目中给的性质，就可以生成一条新的边，也就是从倒数第四个直接联到y，这样的话，每次边的数量都会-2，到最后一定能减少到1，回到之前的情况。所以在同一个连通分量里的左右所有的点一定能连到一起，也就是说所有的方块一定能被涂上。这时候等于说连通分量和能全部染色等价了，我们就只需要计算出来最少需要多少条边使整个图成为连通图就行了。。其实也就是 连通分量数-1

wa点的话因为把n+m写成了2*n错了还以为横纵坐标是一样大的。。。愚蠢的错误emmmm

#include

using namespace std;

typedef long long LL;
const int maxn=2e5+5;
const int mod=1e9+9;

int p[maxn<<1],rak[maxn<<1];
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,q,x,y,cnt,xx,yy;
    cin>>n>>m>>q;
    cnt=n+m;
    for (int i=1;i<=n+m;i++)p[i]=i;
    for (int i=1;i<=q;i++)
    {
        cin>>x>>y;
        y+=n;
        xx=find(x),yy=find(y);
        if(xx==yy)continue;
        cnt--;
        if(rak[xx]