CSAcademy Round #37 : D. Reconstruct Graph

Cで想定誤解法にまんまと引っかかったり、Eでツメが甘かったり微妙。
https://csacademy.com/contest/round-37/task/reconstruct-graph/

問題

N頂点の単純連結無向グラフを考える。
各頂点から先頭の頂点までの距離D[i]が与えられる。
また、M本の辺が与えられる。

これらM本の辺をもち、かつ距離に関する制約を満たす単純連結無向グラフはいくつあるか。

解法

D[v]がdであるような頂点群をS(d)とする。
S(0)、S(1)、…とdの小さい順にS(d)の頂点の辺の張り方を考える。

各頂点v∈S(d)は、以下を満たすように辺を張る。

• D[v']＜D[v]-1となる頂点v'には辺を張ってはならない。
• vからはS(d-1)中の頂点v'に最低1本辺を張らなければならない。
• S(d)内の頂点同士は辺を張っても張らなくてもよい。

ll mo=1000000007;

int N,M;
int D[101010];
vector<int> E[101010];
vector<int> cand[101010];
int same[101010];
set<int> nei[101010];
int mad;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>D[i];
		cand[D[i]].push_back(i);
		mad=max(mad,D[i]);
	}
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		if(D[x]==D[y]) {
			same[x]++;
		}
		else {
			if(D[x]>D[y]) swap(x,y);
			
			if(D[x]+1==D[y]) nei[y].insert(x);
			else return _P("0\n");
		}
	}
	
	if(cand[0].size()!=1) return _P("0\n");
	
	ll ret=1;
	for(i=1;i<=mad;i++) {
		int tar=cand[i-1].size();
		// clo
		FORR(e,cand[i]) {
			int need=nei[e].size();
			
			if(need>0) {
				(ret *= modpow(2,tar-need))%=mo;
			}
			else {
				(ret *= modpow(2,tar)+mo-1)%=mo;
			}
		}
		// same;
		ll x=cand[i].size();
		ll ne=x*(x-1)/2;
		FORR(e,cand[i]) ne-=same[e];
		(ret *= modpow(2,ne))%=mo;
	}
	cout<<ret<<endl;
}

まとめ

これ典型っぽいな。