Codeforces #309 Div1 C. Love Triangles

思いつけばすんなり。
http://codeforces.com/contest/553/problem/C

問題

N人の人がおり、互いの関係は好きか嫌いかいずれかである。
ここで、一部の人間関係だけが判明しており、入力として与えられる。

３人組を考えたとき、以下のいずれかのものを三角関係であるとする。

• ３人が互いに嫌いあっている
• ３つの人間関係のうち２つが好きで１つが嫌い

未判明の人間関係を埋めたとき、三角関係が生じないような組み合わせ数を求めよ。

解法

N人がどういう状態にあると三角形が生じないかを考える。
これは、N人を２グループに分け、同じグループの人は全員好き、別グループの人は全員嫌い、という関係を作れれば良いことになる。
この時、３人組がどのグループの人から選ばれても三角関係が生じない。

よって、まず入力された人間関係をグラフと見なし、２色で色分けしつつ連結成分を求める。
色分けはDFSでもUnion-Findでも良い。
どちらの色に属しても矛盾が生じる(嫌いな人が同じグループにいてしまうor好きな人が別グループにいてしまう)場合、解はない。

ここで連結成分がM個になったとする。
非連結な成分同士のグループの組み合わせは2^(M-1)なので、これが解。

int N,M;
int col[101010];
vector<pair<int,int> > E[101010];
ll mo=1000000007;

void dfs(int cur,int co) {
	if(col[cur]!=-1) {
		if(col[cur]!=co) {
			cout<<0<<endl;
			exit(0);
		}
		return;
	}
	col[cur]=co;
	FORR(r,E[cur]) dfs(r.first,co^r.second);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r^1});
		E[y-1].push_back({x-1,r^1});
	}
	MINUS(col);
	
	ll ret=mo/2+1;
	FOR(i,N) if(col[i]==-1) {
		ret=ret*2%mo;
		dfs(i,0);
	}
	cout<<ret<<endl;
}

まとめ

二部グラフでいい、と気づくまで結構かかってしまった。