福安网站定制,专业做淘宝网站绍兴,android小程序开发,清湖做网站的解析
容易想到补集思想#xff0c;寻找那些组之间不能形成二分图
二分图一般的两个判定方法#xff1a;
染色并查集
这里考虑并查集#xff08;看题解似乎染色也可做#xff09; 先把所有组内的边合并并查集 如果某个组自己内部就有奇环#xff0c;显然不能和任何点配…解析
容易想到补集思想寻找那些组之间不能形成二分图
二分图一般的两个判定方法
染色并查集
这里考虑并查集看题解似乎染色也可做 先把所有组内的边合并并查集 如果某个组自己内部就有奇环显然不能和任何点配对直接删去并减去其贡献 对于其他的边注意到由于总边数只有5e5级别所以图会非常稀疏 可以使用一些暴力点思路
我们sort一下对于每个集合对(u,v)把其对应的边全部加上判断完毕之后再把边删去 由于并查集需要撤销不路径压缩只按秩合并
代码
#includebits/stdc.h
const int N2e6100;
const int mod1e97;
#define ll long long
using namespace std;
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m,k;ll ans;
int vis[N],col[N];#define oth(u) (un?u-n:un)
int fa[N],siz[N],dis[N],top,u[N],v[N],ori;
int find(int x){return xfa[x]?x:find(fa[x]);}
inline void merge(int x,int y){xfind(x);yfind(y);if(xy) 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);#endifnread();mread();kread();ans1ll*k*(k-1)/2;for(int i1;in*2;i) fa[i]i,siz[i]1;for(int i1;in;i) col[i]read();for(int i1;im;i){int xread(),yread();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};}}oritop;sort(e1,e1num,cmp);for(int i1;inum;){int xe[i].x,ye[i].y,acol[x],bcol[y],flag0;if(vis[a]||vis[b]){i;continue;}if(find(x)find(y)){flag1;}else{merge(x,oth(y));merge(y,oth(x));}i;while(inumcol[e[i].x]acol[e[i].y]b){xe[i].x,ye[i].y;if(find(x)find(y)){flag1;}else{merge(x,oth(y));merge(y,oth(x));}i;}while(top!ori){int xu[top],yv[top];top--;fa[x]x;siz[y]-siz[x];}ans-flag;}printf(%lld\n,ans);
}
