CF1012B Chemical table 题解【二分图】【构造】

有意思的网格图转化。CF Div.1 还是挺有难度的。

题解：

一开始总在找规律，比如先放没放过的行或列，先把给出的元素全部聚变一遍……

实际上在这个网格图中，我们把每行、每列均抽象为一个点，可以看成是一个二分图，每个点连接了它的行和列。

那么当一对行、列连通而它们之间又没有直接连边时，可以通过它的路径生成同时在这一行且在这一列的那个点。因此不需要直接连边。

那么我们计算把整个二分图连通需要多少条边，就是连通块个数-1。

Code：

#include<cstdio>

#include<cstring>

struct edge

{

    int n,nxt;

    edge(int n,int nxt)

    {

        this->n=n;

        this->nxt=nxt;

    }

    edge(){}

}e[400100];

int head[400100],ecnt=-1;

void add(int from,int to)

{

    e[++ecnt]=edge(to,head[from]);

    head[from]=ecnt;

    e[++ecnt]=edge(from,head[to]);

    head[to]=ecnt;

}

bool used[400100];

int dfs(int x)

{

    used[x]=1;

    for(int i=head[x];~i;i=e[i].nxt)

        if(!used[e[i].n])

            dfs(e[i].n);

    return 1;

}

int main()

{

    memset(head,-1,sizeof(head));

    int n,m,k,u,v;

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=k;++i)

    {

        scanf("%d%d",&u,&v);

        add(u,n+v);

    }

    int ans=0;

    for(int i=1;i<=n+m;++i)

        if(!used[i])

            ans+=dfs(i);

    printf("%d\n",ans-1);

    return 0;

}