天下一プログラマーコンテスト2016 予選A : E - 無限グラフ

コードは短いんだよなぁ。
http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualE_a

問題

各整数に対応する頂点が無限個存在するとする。
整数NとM個の整数のペア(A[i],B[i])が与えられる。
各整数kに対し、A[i]+k*NとB[i]+(k+1)*Nが無向辺で結ばれているとする。

こうしてできるグラフの連結成分は何個あるか。

解法

N頂点の有向グラフを考える。
A[i]→B[i]へはコスト1、B[i]→A[i]へはコスト-1で移動できると考える。
未到達の頂点を見つけたら、そこからDFSで閉路を探そう。
頂点vの初回到達時のコストをC[v]とする。次に到達たときのコストがxだとするとき、|C[v]-x|回kが増加する方向に移動することで元の頂点に戻ることができる。
すなわち、v,N+v,2N+v,....はGCD(N,|C[v]-x|)個に分類できる。
この手順を繰り返し、到達可能な頂点が何通りに分類できるかを数え上げよう。

逆に閉路がない場合、v,N+v,2N+v,....はそれぞれ互いに移動不可能なので、無限に連結成分が存在することになる。

int N,M;
int did[101010];
int D[101010];
int hoge;
vector<pair<int,int>> E[101010];

void dfs(int cur,int pre,int d) {
	D[cur]=d;
	did[cur]=1;
	FORR(e,E[cur]) if(e.first!=pre) {
		if(did[e.first]) hoge=__gcd(hoge,abs(d+e.second-D[e.first]));
		else dfs(e.first,cur,d+e.second);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back({y,1});
		E[y].push_back({x,-1});
	}
	
	int ret=0;
	FOR(i,N) if(did[i]==0) {
		hoge=0;
		dfs(i,-1,0);
		if(hoge==0) return _P("-1\n");
		ret += hoge;
	}
	
	cout<<ret<<endl;
}

まとめ

本番周期性とか関係するんだろうなぁとは思ったけど、解には至れなかった。