Codeforces #1041 : D. Root was Built by Love, Broken by Destiny

最近Codeforcesの成績奮わないな…。
https://codeforces.com/contest/2127/problem/D

問題

川の両側に合計N個の家があるとする。
また、M個の橋があり、i番目の橋は対岸にある家U[i]と家V[i]をつなぐ。
橋同士が端点以外で交差しないような家の並び順は何通りか。

解法

次数2以上の家を1つ選び、そこを固定して残りの家の配置を考える。
最初の家をRとする。そことつながる家の並び順のうち、次数2以上の家は両端に置くしかないので2個までしか置けない。
あとは再帰的に隣接する次数2以上の家の先の並び方を定めていこう。

int T,N,M;
vector<int> E[202020];
const ll mo=1000000007;

const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll dfs(int cur,int pre) {
	ll ret=0;
	vector<int> C;
	int D=0;
	FORR(e,E[cur]) if(e!=pre) {
		if(E[e].size()==1) D++;
		else C.push_back(e);
	}
	if(C.empty()) return fact[D];
	if(C.size()>1) return 0;
	return fact[D]*dfs(C[0],cur)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) E[i].clear();
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		if(M>=N) {
			cout<<0<<endl;
			continue;
		}
		if(N==2) {
			cout<<2<<endl;
			continue;
		}
		
		ll ret=0;
		FOR(i,N) if(E[i].size()>=2) {
			vector<int> C;
			int D=0;
			FORR(e,E[i]) {
				if(E[e].size()==1) D++;
				else C.push_back(e);
			}
			
			if(C.empty()) {
				ret=fact[D]*2%mo;
			}
			else if(C.size()==1) {
				ret=fact[D]*4*dfs(C[0],i)%mo;
			}
			else if(C.size()==2) {
				ret=fact[D]*4*dfs(C[0],i)%mo*dfs(C[1],i)%mo;
			}
			else {
				ret=0;
			}
			
			break;
		}
		cout<<ret<<endl;
		
	}
}

まとめ

これはC問題というかDiv1 A相当でもいい気はする。