誤読

文字通りくそコード

Lowlinkと橋全列挙と関節点全列挙

HOJのこれ
Hamako Online Judge
を解こうとして、関節点かぁ~ってなったのでLowlinkと関節点とついでに橋を書いた
灘のパソコン部の部誌は有用

平面座標を1次元に直すとき*wってやるのほんとやめような
実際期末試験 on Twitter: "は? https://t.co/BD6vz8wDqv"

グラフ系が割と充実してきて良い

Lowlink:

void Lowlink(BiDGraph& g,vector<int>& lowlink, BiDGraph& dfsg, vector<int>& orb, int st = 0) {
	orb.resize(g.vn, INT_MAX);
	lowlink.resize(g.vn, INT_MAX);
	int k = 0;
	function<void(int,int)> dfs = [&](int cur, int f) {
		int nex = 0;
		orb[cur] = k++;
		lowlink[cur] = orb[cur];
		for (auto itr : g.g[cur]) {
			if (f == itr.first) continue;
			if (orb[itr.first] == INT_MAX) {
				dfs(itr.first,cur);
				lowlink[cur] = min(lowlink[cur], lowlink[itr.first]);
				dfsg.con(cur,itr.first);
			}
			else {
				lowlink[cur] = min(lowlink[cur], orb[itr.first]);
			}
		}
	};
	dfs(st,-1);
	return;
}

関節点:

void Joint(BiDGraph& g, vector<int>& joints, int st = 0) {
	vector<int> lowlink, orb; 
	BiDGraph dfsg(g.vn);
	Lowlink(g, lowlink, dfsg, orb, st);

	REP(i,dfsg.vn) {
		if (st == i) continue;
		if (orb[i] == INT_MAX) continue;
		for (auto itr : dfsg.g[i]) {
			if (orb[itr.first] == INT_MAX) continue;
			if (orb[i] > orb[itr.first]) continue;

			if (orb[i] <= lowlink[itr.first]) {
				joints.push_back(i);
				break;
			}
		}
	}
	if(dfsg.g[st].size() > 1)
		joints.push_back(st);
}

void Bridge(BiDGraph& g, vector<pii>& bridges, int st = 0) {
	vector<int> lowlink, orb;
	BiDGraph dfsg(g.vn);
	Lowlink(g, lowlink, dfsg, orb, st);

	REP(i, dfsg.vn) {
		for (auto itr : dfsg.g[i]) {
			if (orb[i] > orb[itr.first]) continue;

			if (orb[i] < lowlink[itr.first]) {
				bridges.push_back({ i, itr.first });
			}
		}
	}
}