KUPC 2014 C - 占い

問題

A, BがいてAが数列a[i], Bが数列b[i]を持っている。
a[i]の長さはn, b[i]の長さはmである。

a[x[i]] = b[y[i]]という関係x[i], y[i]がc個与えられる。

二人が一緒に数を書いていく。
Aはk回目にa[k % n]を書いて、Bはk回目にb[k % m]を書く。
二人の数字が異なったら終了。
ただし、無限に終わらないa[i], b[i]のときは最初から数字を1個も書けないものとする。
二人は最大で何個の数字を書けるか。

方針

union-findで数字が同じである関係を、根が同じであるという関係として管理する。
根が違うノードが来たら、マージしてやる。
最後にマージしたのがi回目に書いた数字だとすると、iが答え。

LCM(n, m)回だけループをまわせばa[0], b[0]からに戻るので、
LCM(n, m)回だけ見れば十分だけど、制約が小さいのでn * m回まわして間に合う。

ソースコード

int n, m, q;
int p[500];
int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}
int main(){
	cin >> n >> m >> q;
	rep(i, n + m) p[i] = i;
	rep(i, q){
		int a, b; cin >> a >> b;
		a--; b--;
		a = root(a); b = root(b + n);
		if(a != b) p[b] = a;
	}
	int ans = 0;
	int a = 0, b = 0;
	
	rep(i, n * m){
		
		int x = root(a), y = root(b + n);
		if(x != y){
			ans = i + 1;
			p[y] = x;
		}
		a = (a + 1) % n; b = (b + 1) % m;
	}
	cout << ans << endl;
	
	return 0;
}