题目链接：点击查看
题目大意：给出一张有 n 个点和 m 条边的图，每个点都有一个种类，共有 k 个种类，现在要从 k 个种类中每次选出两种，对所有 C( k , 2 ) 种组合单独讨论，对于选出的两个种类中，包含的所有的点以及其连边所组成的子图，如果该子图可以拆分成二分图，那么答案加一
题目分析：参考博客：https://blog.csdn.net/Zenith_Habitant/article/details/109451857
k 的范围很大，正难则反，考虑计算不合法的组合个数，然后由总的合法个数减去就是答案了
首先看到题目中的二分图，不难想到其定义为：“不含有奇环的一个图”，而判断二分图的两种方法，一种是直接 dfs 染色，另一种方法就是对每个点建立虚点然后并查集维护，可以参考：CH - 4901 关押罪犯
因为总的边数只有 m 条边，换句话说，假设每条边 ( x , y ) 连接的 x 和 y 都属于不同的种类，最终也只有 m 种组合方案，所以非法的种类数最多只有 m 种
所以对于每条边 ( x , y ) 分类讨论，设 type[ x ] 是 x 的种类：
如果 type[ x ] == type[ y ]，直接用并查集将其合并即可如果 type[ x ] != type[ y ]，将其加入所有，连接( type[ x ] , type[ y ] ) 这两个种类的边的集合中去
然后对于每个种类自己单独的连通块内，如果出现了奇环，说明当前这个种类无论和哪个组合匹配，都不可能产生贡献了，对于这些种类单独拿出来即可
然后就是对合并任意两个种类的那些边分组，依次合并，看看这两个种类组合的话是否会产生贡献，这里需要注意的是，因为对于合并每两个组的边集都是相互独立的，所以在进行完一次 “ 合并 ”，检查出答案后，需要及时撤销，这样就可以保证算法的正确性了，关于撤销可以直接用并查集的撤销来实现
代码：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;map<pair<int,int>,vector<pair<int,int>>>mp;//map[{type_a,type_b}]={(u1,v1),(u2,v2)...(uk,vk)}//表示连接两个组的边 struct revo
{int fax,fay;int rkx,rky;
};int a[N],b[N],f[N],rk[N],type[N],tot;bool fail[N];stack<revo>st;int find(int x)
{return f[x]==x?x:find(f[x]);
}void merge(int x,int y)
{int xx=find(x),yy=find(y);revo temp;temp.fax=xx,temp.fay=yy;temp.rkx=rk[xx],temp.rky=rk[yy];st.push(temp);if(rk[xx]>rk[yy])swap(xx,yy);f[xx]=yy;rk[yy]=max(rk[yy],rk[xx]+1);
}void revocation(int k)
{while(k--){revo node=st.top();st.pop();f[node.fax]=node.fax;f[node.fay]=node.fay;rk[node.fax]=node.rkx;rk[node.fay]=node.rky;}
}void init()
{for(int i=1;i<N;i++){f[i]=i;rk[i]=1;}
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);init();int n,m,k;LL ans=0;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)scanf("%d",type+i);for(int i=1;i<=m;i++)scanf("%d%d",a+i,b+i);for(int i=1;i<=m;i++)//同一种类的边，直接维护即可 {if(type[a[i]]==type[b[i]]){int xx=find(a[i]),yy=find(b[i]);if(xx!=yy)merge(a[i],b[i]+n),merge(b[i],a[i]+n);elsefail[type[a[i]]]=true;}}for(int i=1;i<=m;i++)//连接两个不同种类的边，将其归类 {if(type[a[i]]==type[b[i]])continue;if(fail[type[a[i]]]||fail[type[b[i]]])continue;if(type[a[i]]>type[b[i]])swap(a[i],b[i]);mp[make_pair(type[a[i]],type[b[i]])].emplace_back(a[i],b[i]);}for(auto node:mp)//node.second=vector<pair<int,int>>{int cnt=0;for(auto it:node.second)//it=pair<int,int>=(u,v){int x,y;tie(x,y)=it;int xx=find(x),yy=find(y);if(xx!=yy)merge(x,y+n),merge(y,x+n),cnt+=2;else{ans--;break;}}revocation(cnt);}LL cnt=0;for(int i=1;i<=k;i++)if(!fail[i])cnt++;ans+=cnt*(cnt-1)/2;printf("%lld\n",ans);return 0;
}
总结
以上是生活随笔为你收集整理的CodeForces - 1445E Team-Building(可撤销并查集)的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
