解析

容易想到补集思想，寻找那些组之间不能形成二分图

二分图一般的两个判定方法：

染色

并查集

这里考虑并查集（看题解似乎染色也可做）
先把所有组内的边合并并查集
如果某个组自己内部就有奇环，显然不能和任何点配对，直接删去并减去其贡献
对于其他的边，注意到，由于总边数只有5e5级别，所以图会非常稀疏
可以使用一些暴力点思路

我们sort一下，对于每个集合对(u,v)，把其对应的边全部加上，判断完毕之后，再把边删去
由于并查集需要撤销，不路径压缩，只按秩合并

代码

#include<bits/stdc++.h> const int N=2e6+100; const int mod=1e9+7; #define ll long long using namespace std; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,k;ll ans; int vis[N],col[N];#define oth(u) (u>n?u-n:u+n) int fa[N],siz[N],dis[N],top,u[N],v[N],ori; int find(int x){return x==fa[x]?x:find(fa[x]);} inline void merge(int x,int y){x=find(x);y=find(y);if(x==y) return;if(siz[x]>siz[y]) swap(x,y);fa[x]=y;siz[y]+=siz[x];++top;u[top]=x;v[top]=y;return; }struct edge{int x,y; }e[N]; int num; bool cmp(edge a,edge b){if(col[a.x]!=col[b.x]) return col[a.x]<col[b.x];else return col[a.y]<col[b.y]; }int main(){#ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);#endifn=read();m=read();k=read();ans=1ll*k*(k-1)/2;for(int i=1;i<=n*2;i++) fa[i]=i,siz[i]=1;for(int i=1;i<=n;i++) col[i]=read();for(int i=1;i<=m;i++){int x=read(),y=read();if(col[x]==col[y]){if(find(x)==find(y)){if(!vis[col[x]]) ans-=--k;vis[col[x]]=1;}else{merge(x,oth(y));merge(y,oth(x));}}else{if(col[x]>col[y]) swap(x,y);e[++num]=(edge){x,y};}}ori=top;sort(e+1,e+1+num,cmp);for(int i=1;i<=num;){int x=e[i].x,y=e[i].y,a=col[x],b=col[y],flag=0;if(vis[a]||vis[b]){++i;continue;}if(find(x)==find(y)){flag=1;}else{merge(x,oth(y));merge(y,oth(x));}i++;while(i<=num&&col[e[i].x]==a&&col[e[i].y]==b){x=e[i].x,y=e[i].y;if(find(x)==find(y)){flag=1;}else{merge(x,oth(y));merge(y,oth(x));}i++;}while(top!=ori){int x=u[top],y=v[top];top--;fa[x]=x;siz[y]-=siz[x];}ans-=flag;}printf("%lld\n",ans); }

总结

以上是生活随笔为你收集整理的CF1444C Team-Building（可持久化并查集）（二分图）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。