AtCoder ARC #105 : E - Keep Graph Disconnected

うーん、こういうゲーム系苦手。
https://atcoder.jp/contests/arc105/tasks/arc105_e

問題

N頂点M辺の無向グラフが与えられる。
初期状態で頂点1とNは非連結である。
ここで2人で交互に辺を1本追加するゲームを行う。

辺を追加する際、多重辺やループを作ってはならない。
また、頂点1とNが連結になってはならない。
両者最適手を取るとき、勝者はどちらか。

解法

自分の手番で、完全グラフ×2の形にすると次に相手が詰む。
Nが奇数の時、完全グラフ×2となったときに存在する辺の数の偶奇は固定なので、詰む手番は辺の数の偶奇だけ見れば確定できる。
Nが偶数の時、完全グラフ×2となったときに両者の頂点数が偶数・偶数か奇数・奇数かで辺の数の偶奇が変化するので、勝者はそこまでの手順できまる。

初期状態で頂点1とNの連結成分の頂点数の偶奇が分かれているとき、先手必勝である。
初手で先手が偶数・偶数か奇数・奇数のうち勝てるほうに遷移させておくと、後手が偶数・奇数のパターンにしても戻せるし、後手が偶数・偶数か奇数・奇数をキープしようとしたとき、先手も再度それをキープできる辺が余っている。

問題は初期状態で先手が偶数・偶数か奇数・奇数のうち勝てない方になっている場合、毎ターン先手の行動は反対に後手に押し戻されるので後手必勝。

int T;
int N,M;
int win[101010];

class UF {
	public:
	vector<int> par,rank,cnt;
	void reinit(int num) {par=rank=vector<int>(num,0); cnt=vector<int>(num,1); for(int i=0;i<num;i++) par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		uf.reinit(N);
		FOR(i,M) {
			cin>>x>>y;
			x--,y--;
			uf(x,y);
		}
		vector<int> V;
		V.push_back(uf.count(0));
		V.push_back(uf.count(N-1));
		for(i=1;i<N-1;i++) if(uf[i]==i&&uf[i]!=uf[0]&&uf[i]!=uf[N-1]) V.push_back(uf.count(i));
		
		int C[2]={};
		for(i=uf.count(0);i<=N-uf.count(N-1);i++) {
			ll tot=1LL*i*(i-1)/2+1LL*(N-i)*(N-i-1)/2;
			ll add=tot-M;
			win[i]=(add%2)^1;
			C[win[i]]++;
		}
		
		if(C[0]==0) {
			cout<<"Second"<<endl;
		}
		else if(C[1]==0) {
			cout<<"First"<<endl;
		}
		else {
			if(V[0]%2!=V[1]%2) {
				cout<<"First"<<endl;
			}
			else {
				ll a=1LL*N*(N-1)/2-1LL*V[0]*V[1]-M;
				if(a%2==0) {
					cout<<"Second"<<endl;
				}
				else {
					cout<<"First"<<endl;
				}
			}
		}
	}
}

まとめ

こういうの自信をもって書けないなぁ。