AtCoder ABC #142 : F - Pure

ちょっと手間取った。
https://atcoder.jp/contests/abc142/tasks/abc142_f

問題

有向グラフが与えられる。
このグラフの誘導部分グラフのうち、空ではなく、かつ全頂点の入次数・出次数が1となるものが存在するならそれをもとめよ。

解法

次数に関する頂点は、頂点が閉路を成しており、かつ閉路が誘導部分グラフ内で分岐を持たずループになっていることを意味する。
ループが２個以上からなる誘導部分グラフも条件を満たすが、この問題にはそれは要求されないのでループが１つの物を見つけよう。

まず、適当に同じ頂点を２回以上通らない閉路を見つける。
誘導部分グラフ内の分岐の有無は問わないので、これは定番の問題である。

例えばA→B→C→D→E→F→A…と閉路を成していたとする。

次に、これが次数に関する条件を満たすかチェックしよう。
もし条件を満たさない場合、途中で分岐がある。例えばE→Bなんて辺もあるかもしれない。
そうしたら、その辺を用いてより小さな閉路を作ろう。
例えばE→Bという経路があるなら、F,Aは削除してB→C→D→E→B→…としよう。

同様に分岐の有無を確認する。
もし分岐があればそのつどより小さい閉路が作れるので、この処理はいずれ終わる。
分岐がなくなったらその時点の閉路を答えればよい。

int N,M;
vector<int> E[1010];
int vis[1010];
vector<int> V,C;
int id[1010];

void dfs(int cur) {
	if(vis[cur]==2) {
		if(C.empty()) {
			int i,j;
			FOR(i,V.size()) if(V[i]==cur) {
				for(j=i;j<V.size();j++) {
					C.push_back(V[j]);
					id[V[j]]=j-i;
				}
				break;
			}
		}
		return;
	}
	if(vis[cur]==1) return;
	vis[cur]=2;
	V.push_back(cur);
	FORR(e,E[cur]) dfs(e);
	V.pop_back();
	vis[cur]=1;
}

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);
	}
	
	MINUS(id);
	FOR(i,N) {
		ZERO(vis);
		V.clear();
		dfs(i+1);
	}
	
	if(C.empty()) return _P("-1\n");
	retry:
	FOR(i,C.size()) {
		FORR(e,E[C[i]]) if(id[e]!=-1 && id[e]!=(id[C[i]]+1)%C.size()) {
			vector<int> C2;
			y=id[e];
			MINUS(id);
			FOR(j,C.size()) {
				C2.push_back(C[(y+j)%C.size()]);
				id[C[(y+j)%C.size()]]=j;
				if((y+j)%C.size()==i) break;
			}
			swap(C,C2);
			goto retry;
		}
	}
	
	cout<<C.size()<<endl;
	FORR(c,C) cout<<c<<endl;
	
}

まとめ

変な凡ミスしてもったいなかった。