SRM 228 DIV1 Hard Loopy

問題 Editorial

問題

略。あまりわかってない

解答

Practice Roomのiwiさんの解答を参考にした。
"entry"ステートメントとループの末尾を全探索する。
そしてうまい感じでdfsする感じの感じ。わかってない。
末尾からグラフを逆にentryに達するまで見ていき、デッドコードでないならentryから到達できる必要がある。
何故なら、entryから到達できないならループには入れないが、(そこ→末尾)というふうに、ループ外からループ内に入ることになるため。
entryから到達できるなら、ループに含まれないといけない。末尾からループ内に入るから。
それで到達できた所を数えればいい。

コメント

うまいdfsの感じ、苦手だな。
そもそも問題もあまり良くわかっていない感じもあって。
どうでもいいけど、ttp://d.hatena.ne.jp/chokudai_pre/20090126/1232952987 にあるように、過去に日本のみんなで練習したことのあるPractice Roomのようだ。

コード

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
bool g[55][55], wf[55][55], ret[55], path[55];
bool vis[55];
struct Loopy {
	int n;
	bool dfs(int i, int entry) {
		if(vis[i]) return true;
		if(!wf[0][i]) return true;
		vis[i] = true;
		if(i == 0 || !wf[entry][i]) return false;
		bool r = true;
		rep(j, n) if(g[j][i]) r &= dfs(j, entry);
		return r;
	}
	int minLoop(vector <string> code) {
		n = code.size();
		mset(g, 0), mset(ret, 0), mset(path, 0), mset(wf, 0);
		rep(i, n) {
			if(code[i][0] == 'I') {
				stringstream ss(code[i]);
				int x, y; string t;
				ss >> t >> x >> t >> y;
				g[i][x] = g[i][y] = true;
			}else ret[i] = true;
		}
		rep(i, n) rep(j, n) wf[i][j] = g[i][j];
		rep(k, n) rep(i, n) rep(j, n) wf[i][j] |= wf[i][k] && wf[k][j];
		rep(i, n) rep(j, n) path[i] |= wf[i][j] && ret[j];
		int r = INF;
		rep(entry, n) if(wf[0][entry] && path[entry]) {
			if(g[entry][entry]) { r = min(r, 1); continue; }
			rep(last, n) if(wf[entry][last] && g[last][entry]) {
				mset(vis, 0); vis[entry] = true;
				if(!dfs(last, entry)) continue;
				r = min(r, count(vis, vis+n, true));
			}
		}
		return r == INF ? 0 : r;
	}
};