Codeforces #680 Div1 C. Team-Building

本番割と手間取ってるな。
http://codeforces.com/contest/1444/problem/C

問題

N人の生徒がK個のグループに分かれている。
また、生徒の間は、M組の仲のいい生徒のペアがいる。

K個のグループから2グループを選ぶとき、それら2グループの生徒を合わせて2つのチームに分けるとき、仲の良い生徒が同じチームにならないような分け方が可能なものは何組か。

解法

生徒の関係を、無向グラフとして考える。
生徒を頂点、仲の良い生徒同士の関係を無向辺としたとき、2グループ内の生徒からなる部分誘導グラフが二部グラフでない場合、問題の分け方は不可能である。

これを用いて、巻き戻し可能なDSUを使い解く。
まず、同一グループ内の時点で、二部グラフにできないものをあらかじめ列挙しよう。
これらのグループは以下無視して考える。

以降は、それ以外のグループ対のうち、条件を満たさないものを消すことを考える。
生徒xの所属グループをG(x)とする。
xとyが仲がいい場合、G(x)とG(y)の間を結ぶ辺をつないでみて、二部グラフを維持できるか見ていくとよい。

int N,M,K;
int C[505050];
vector<int> cand[505050];
map<pair<int,int>,vector<pair<int,int>>> Scand;

template<int um> class UF_pop {
	public:
	vector<int> par,rank; vector<vector<int>> hist;
	UF_pop() {par=rank=vector<int>(um,0); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; hist.clear(); FOR(i,um) rank[i]=0,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):operator[](par[x]);}
	void pop() {
		if(hist.size()) {
			auto a=hist.back();
			hist.pop_back();
			par[a[0]]=a[1]; rank[a[0]]=a[2];
			par[a[3]]=a[4]; rank[a[3]]=a[5];
		}
	}
	void operator()(int x,int y) {
		x=operator[](x); y=operator[](y);
		hist.push_back({x,par[x],rank[x],y,par[y],rank[y]});
		if(x==y) return;
		if(rank[x]<rank[y]) par[x]=y;
		else rank[x]+=(rank[x]==rank[y]), par[y]=x;
	}
};
UF_pop<1010101> uf;
int NG[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&M,&K);
	FOR(i,N) {
		scanf("%d",&C[i]);
		C[i]--;
		cand[C[i]].push_back(i);
	}
	
	FOR(i,M) {
		scanf("%d%d",&x,&y);
		x--,y--;
		if(C[x]==C[y]) {
			uf(2*x,2*y+1);
			uf(2*y,2*x+1);
		}
		else {
			if(C[x]>C[y]) swap(x,y);
			Scand[{C[x],C[y]}].push_back({x,y});
		}
	}
	
	ll ret=0;
	int okK=K;
	FOR(i,K) {
		FORR(c,cand[i]) {
			if(uf[2*c]==uf[2*c+1]) NG[i]=1;
		}
		if(NG[i]) okK--;
	}
	ret=1LL*okK*(okK-1)/2;
	
	FORR(m,Scand) {
		x=m.first.first;
		y=m.first.second;
		if(NG[x]||NG[y]) continue;
		int ng=0;
		FORR(v,m.second) {
			uf(v.first*2,v.second*2+1);
			uf(v.first*2+1,v.second*2);
			if(uf[v.first*2]==uf[v.first*2+1]) ng=1;
		}
		if(ng) ret--;
		FORR(v,m.second) uf.pop(), uf.pop();
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

チームとかグループとかなんかいろいろ混乱しがち。