TopCoder SRM 733 Div1 Medium BuildingSpanningTreesDiv1

これ知識ゲーでなく自力で導き出せた人どのぐらいいるんだろう。
https://community.topcoder.com/stat?c=problem_statement&pm=14880

問題

N頂点の完全グラフがある。
このグラフの全域木のうち、指定された辺集合を持つものは何通りか。

解法

辺集合がすでに閉路を成す場合は解は0。
それ以外の場合、まず指定された辺を用いて頂点をつないだとき、各連結成分の頂点数の数列をS[i]とする。

解はN^(|S|-2)*prod(S)となる。
これはケイリーの公式を導く手順を応用するとわかる。らしい。

ll mo=987654323;

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};




class BuildingSpanningTreesDiv1 {
	public:
	int getNumberOfSpanningTrees(int n, vector <int> X, vector <int> Y) {
		int num[1010]={};
		UF<5000> uf;
		int i,x,y;
		FOR(i,X.size()) {
			X[i]--;
			Y[i]--;
			if(uf[X[i]]==uf[Y[i]]) return 0;
			uf(X[i],Y[i]);
		}
		vector<int> V;
		FOR(i,n) num[uf[i]]++;
		FOR(i,n) if(num[i]) V.push_back(num[i]);
		int C=V.size();
		if(C==1) return 1;
		
		ll ret=1;
		FORR(v,V) (ret*=v)%=mo;
		FOR(i,C-2) (ret*=n)%=mo;
		return ret;
		
	}
}

まとめ

最初NNTを使うテクかと思ったけど、よく見たら剰余をとる値が違った。