CODE FESTIVAL 2014 エキシビジョン : A - パズル

エキシビジョンオープン参加で、なんとかオープン部門のA First Acceptedを取れた。
Bは時間切れ。
http://code-festival-2014-exhibition-open.contest.atcoder.jp/tasks/code_festival_exhibition_a

問題

N点M辺の無向辺グラフがある。
頂点iには、初期状態で頂点番号iが格納されている。

ここで、互いに辺で連結されている３つの頂点があったとき、３頂点に格納される番号を(a,b,c)とすると、(b,c,a)と番号をずらすことができる。これを回転と呼ぶ。

終了状態の頂点の番号Y[i]が与えられる。
回転を任意回数行い、初期状態から終了状態に遷移可能かどうか判定せよ。

解法

まず、初期状態と終了状態の頂点番号が回転で移動可能かどうかを示す。
これは回転できる頂点群をUnion-Findで連結していき、i番とY[i]番の頂点が連結しているか判定すればよい。

３頂点が互いに辺で結ばれているかどうかは、３頂点を総当たりするとO(N^3)で間に合わない。
しかし、２辺を列挙してその２辺が１つの点を共有し、かつ残りの２点を結ぶ別の辺があるかどうか、という判定にするとO(M^2)ですむ。
今回はMがNと同程度で小さいので、こちらで判定するとよい。

これでY[i]番の頂点番号をi番に持ってこれることは判定できたとして、15パズルのように最後２頂点の番号が逆になってしまう可能性がある。
頂点番号を(1,2,3)の状態から回転して得られる状態(2,3,1)、(3,1,2)はいずれも転置数が偶数である。
よって、上記逆転の有無を判定するには、各連結成分において転置数の偶奇を調べればよい。

class UF {
	public:
	static const int ufmax=100052;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[find(x)];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N,M;
int A[2001],B[2001];
int Y[2001];
int mat[2001][2001];
int ten[2001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	UF uf;
	FOR(i,M) {
		cin>>A[i]>>B[i];
		A[i]--,B[i]--;
		mat[A[i]][B[i]]=mat[B[i]][A[i]]=1;
	}
	FOR(i,N) {
		cin>>Y[i];
		Y[i]--;
	}
	FOR(x,M) for(y=x+1;y<M;y++) {
		int un=0;
		if(A[x]==A[y] && mat[B[x]][B[y]]) un++;
		if(A[x]==B[y] && mat[B[x]][A[y]]) un++;
		if(B[x]==A[y] && mat[A[x]][B[y]]) un++;
		if(B[x]==B[y] && mat[A[x]][A[y]]) un++;
		if(un) {
			uf.unite(A[x],A[y]);
			uf.unite(B[x],B[y]);
			uf.unite(A[x],B[x]);
			uf.unite(A[x],B[y]);
			uf.unite(A[y],B[x]);
			uf.unite(A[y],B[y]);
		}
	}
	FOR(i,N) if(uf[i]!=uf[Y[i]]) return _P("NO\n");

	j=0;
	FOR(x,N) for(y=x+1;y<N;y++) if(uf[x]==uf[y] && Y[x]>Y[y]) ten[uf[x]]++;
	FOR(i,N) if(ten[i]%2) return _P("NO\n");
	
	_P("YES\n");
}

まとめ

とっさに転置数の事を思い出してよかった。