题解 CF1444C 【Team-Building】

· · 题解

题意：给定一张点有类型的无向图，求有多少组无序类型对 (a,b) 使得两种类型节点的导出子图是二分图。

众所周知，二分图判定等价于奇环存在性，那么奇环只会出现在类型内部和类型之间。能对答案贡献的类型必定没有奇环，可以先对每个类型 dfs 染色判定。判定得到以下值：f_i 表示 i 属于第 f_i 个连通块，g_i 表示其被染色 i。

接下来就是考虑哪些剩下的类型对之间不成奇环，显然数目是非常大的，考虑转化为求哪些类型对成奇环。显然类型对能成奇环的必要条件是类型对之间有边，可以考虑将类间边按照端点所属类型排序一起处理，这样需要处理的类型对数目是 O(m) 的。

考虑一个类型对时，建立一张新图，设类间连边 (u,v)，若 g_u=g_v 则连边 (f_u,f_v) 表示 f_u,f_v 的标色是反的，否则连边 (f_u,newnode),(newnode,f_v) 表示 f_u,f_v 的标色相同，则显然原图不矛盾当且仅当新图是二分图，对新图再跑个二分图判定即可。

复杂度 O(n+m) 或 O(n+m\log m)，取决于排序是快排还是基排。由于没有并查集，复杂度并没有 \alpha。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
const int N=2e6+2;
vector<int> lb[N],bh[N];
ll ans;
int bel[N],ed[N],f[N],nf[N],app[N],fir[N],nxt[N],lj[N];
int n,c,fh,i,j,k,t,x,y,m,bs,q,tp,cnt,cur,atp,ld;
bool av[N],ned[N];
struct Q
{
    int bu,bv,u,v;
    Q(int a=0,int b=0):bu(bel[a]),bv(bel[b]),u(a),v(b){}
    bool operator<(const Q &o) const {return (bu<o.bu)||(bu==o.bu)&&(bv<o.bv);}
};
Q st[N];
inline void add(int x,int y)
{
    lj[++bs]=y;
    nxt[bs]=fir[x];
    fir[x]=bs;
    lj[++bs]=x;
    nxt[bs]=fir[y];
    fir[y]=bs;
}
inline void read(int &x)
{
    c=getchar();fh=1;
    while ((c<48)||(c>57))
    {
        if (c=='-') {c=getchar();fh=-1;break;}
        c=getchar();
    }
    x=c^48;c=getchar();
    while ((c>=48)&&(c<=57))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    x*=fh;
}
void dfs1(int x,int y)
{
    ed[x]=cnt;f[x]=y;
    for (int i=0;i<lb[x].size();i++) if (!ed[lb[x][i]]) dfs1(lb[x][i],y^1); else
    {
        if (y==f[lb[x][i]]) {av[cur]=0;return;}
    }
}
void dfs2(int x,int y)
{
    //printf("dfs2 %d %d\n",x,y);
    ned[x]=1;nf[x]=y;
    for (int i=fir[x];i;i=nxt[i]) if (!ned[lj[i]]) dfs2(lj[i],y^1); else
    {
        if (y==nf[lj[i]]) {av[cur]=0;return;}
    }
}
int main()
{
    //freopen("a.in","r",stdin);
    read(n);read(m);read(q);
    for (i=1;i<=n;i++) {read(bel[i]);bh[bel[i]].push_back(i);}
    while (m--)
    {
        read(x);read(y);if (bel[x]!=bel[y])
        {
            if (bel[x]>bel[y]) swap(x,y);
            st[++tp]=Q(x,y);
        } else lb[x].push_back(y),lb[y].push_back(x);
    }
    for (i=1;i<=q;i++) av[i]=1;ld=n;
    for (i=1;i<=q;i++)
    {
        cur=i;
        for (j=0;(j<bh[i].size())&&(av[cur]);j++) if (!ed[bh[i][j]]) {++cnt;dfs1(bh[i][j],0);}
    }cnt=0;
    for (i=1;i<=q;i++) if (!av[i]) ++cnt;
    ans=(ll)(q-cnt)*(q-cnt-1)>>1;
    sort(st+1,st+tp+1);
    for (i=1;i<=tp;i=j+1)
    {
        j=i;
        while ((j<tp)&&(st[j+1].bu==st[i].bu)&&(st[j+1].bv==st[i].bv)) ++j;
        if (!(av[st[i].bv]&&av[st[i].bu])) continue;
        atp=0;
        for (k=i;k<=j;k++)
        {
            //if ((st[k].bu==2)&&(st[k].bv==3)) printf("%d %d %d %d %d\n",st[k].u,st[k].v,(int)f[st[k].u]==f[st[k].v],ed[st[k].u],ed[st[k].v]);
            if (f[st[k].u]==f[st[k].v])
            {
                add(ed[st[k].u],++ld);
                add(ld,ed[st[k].v]);
            } else add(ed[st[k].u],ed[st[k].v]);
            if (!ned[ed[st[k].u]]) app[++atp]=ed[st[k].u],ned[ed[st[k].u]]=1;
            if (!ned[ed[st[k].v]]) app[++atp]=ed[st[k].v],ned[ed[st[k].v]]=1;
        }
        for (k=1;k<=atp;k++) ned[app[k]]=0;
        av[cur=i+q]=1;
        for (k=1;(k<=atp)&&(av[cur]);k++) if (!ned[app[k]]) dfs2(app[k],0);
        if (!av[cur]) --ans;
        //printf("%d:%d %d\n",(int)av[cur],st[i].bu,st[i].bv);
        for (k=1;k<=atp;k++) fir[app[k]]=0,ned[app[k]]=0;bs=0;
    }
    printf("%lld",ans);
}