Codeforces #594 Div1 D. Catowice City

解法は割とあっさり。
https://codeforces.com/contest/1239/problem/D

問題

N個の家があり、それぞれ1人の人間と1人の猫が住んでいる。
各建物の人間は、同じ建物の猫を知っており、それ以外にも何匹かの猫を知っている。

ここで各家から、人か猫のいずれか1人(1匹)ずつ計N体を連れてくることを考える。
その際、人と猫が知り合いになるような組み合わせを作らずに済むことができるか。

解法

N頂点の有効グラフを考える。
人と猫の知り合い関係に沿って、有効辺を張ろう。

ここで閉路を構築している頂点内は、人と猫を全体でどちらかしか選択できない。
そこで、元のグラフを強連結成分分解してみる。
連結成分が1なら解なし。
2以上なら、連結成分間がDAGを成すので根に相当する連結成分を猫とし、残りを人とできる。

int T;
int N,M;

class SCC {
public:
	static const int MV = 2025000;
	vector<vector<int> > SC; int NV,GR[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<NV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0,i; SC.clear(); SC.resize(NV); NUM.clear();
		assert(NV);
		FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0;
		for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};

SCC scc;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&M);
		scc.init(N);
		FOR(i,M) {
			scanf("%d%d",&x,&y);
			if(x!=y) scc.add_edge(x-1,y-1);
		}
		scc.scc();
		vector<int> A,B;
		FOR(i,N) {
			if(scc.GR[i]==0) B.push_back(i+1);
			else A.push_back(i+1);
		}
		if(B.size()==N) {
			_P("No\n");
		}
		else {
			_P("Yes\n");
			_P("%d %d\n",A.size(),B.size());
			FORR(a,A) _P("%d ",a);
			_P("\n");
			FORR(b,B) _P("%d ",b);
			_P("\n");
		}
	}
}

まとめ

Div1 Dとしてはシンプル。