#1157134 (C++23) No.3463 Beltway

• 問題: No.3463 Beltway
• ユーザー: kwm_t
• 提出日時: 2026-04-12 15:18:54
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 85 ms / 2,000 ms
• コード長: 4,237 bytes
• コンパイル時間: 3,407 ms
• コンパイル使用メモリ: 357,464 KB
• 実行使用メモリ: 72,336 KB
• 最終ジャッジ日時: 2026-04-12 15:19:00
• 合計ジャッジ時間: 6,471 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	AC * 17

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_GRAPH_LOWLINK_HPP
#define KWM_T_GRAPH_LOWLINK_HPP

#include <vector>
#include <algorithm>
#include <iostream>

/**
 * @brief Lowlink（関節点・橋・2点間の橋必須判定）
 *
 * 典型用途:
 *   - 関節点（articulation points）の列挙
 *   - 橋（bridge）の列挙
 *   - 辺が s-t パスに必ず含まれるか判定
 *
 * 計算量:
 *   - 構築: O(N + M)
 *   - クエリ: O(1)
 *
 * @param グラフは (to, edge_id) を持つ隣接リスト
 *
 * 制約 / 注意:
 *   - 無向グラフで使用すること
 *   - edge_id は 0..M-1 の範囲であること
 *
 * 使用例:
 *   Lowlink ll(G, M);
 *   ll.build();
 *   auto aps = ll.articulation_points;
 *
 * verified:
 *   - AOJ GRL_3_A, GRL_3_B
 */
namespace kwm_t::graph {

class Lowlink {
private:
	using Edge = std::vector<std::vector<std::pair<int, int>>>;

public:
	int sz;
	int m;
	Edge G;

	// 関節点
	std::vector<int> articulation_points;

	// 橋 (edge_id -> 子頂点, -1なら橋でない)
	std::vector<int> bridge;

	// DFS木の根
	std::vector<bool> is_root;

private:
	std::vector<int> in, out, low;
	std::vector<std::vector<int>> child;

public:
	Lowlink(const Edge& G, int m) : G(G), m(m) {}

	void build() {
		sz = G.size();

		in.assign(sz, -1);
		out.assign(sz, -1);
		low.assign(sz, -1);
		child.assign(sz, {});
		is_root.assign(sz, false);

		bridge.assign(m, -1);

		int k = 0;
		for (int i = 0; i < sz; ++i) {
			if (in[i] < 0) {
				is_root[i] = true;
				dfs(i, -1, k);
			}
		}
	}

	/**
	 * @brief 頂点 v を削除したときの連結成分数
	 */
	int remove(int v) const {
		int c = 0;
		for (int nv : child[v]) {
			if (in[v] <= low[nv]) c++;
		}
		if (!is_root[v]) c++;
		return c;
	}

	/**
	 * @brief 辺 a が s-t パスに必ず含まれるか
	 */
	bool query(int a, int s, int t) const {
		if (bridge[a] == -1) return false;

		int l = in[bridge[a]];
		int r = out[bridge[a]];

		s = in[s];
		t = in[t];

		return ((l <= s && s < r) ^ (l <= t && t < r));
	}
private:
	void dfs(int v, int p_edge, int& k) {
		in[v] = low[v] = k++;
		bool is_art = false;

		for (auto[nv, id] : G[v]) {
			if (in[nv] < 0) {
				child[v].push_back(nv);
				dfs(nv, id, k);

				low[v] = std::min(low[v], low[nv]);

				// 関節点判定
				if (p_edge != -1 && in[v] <= low[nv]) {
					is_art = true;
				}

				// 橋判定
				if (in[v] < low[nv]) {
					bridge[id] = nv;
				}
			}
			else if (id != p_edge) {
				low[v] = std::min(low[v], in[nv]);
			}
		}

		// 根の場合
		if (p_edge == -1 && child[v].size() >= 2) {
			is_art = true;
		}

		if (is_art) {
			articulation_points.push_back(v);
		}

		out[v] = k++;
	}
};

} // namespace kwm_t::graph

#endif // KWM_T_GRAPH_LOWLINK_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int v, e, s, g; cin >> v >> e >> s >> g;
	s--, g--;
	vector to(v, vector<P>());
	rep(i, e) {
		int p, q; cin >> p >> q;
		p--, q--;
		to[p].emplace_back(q, i);
		to[q].emplace_back(p, i);
	}
	kwm_t::graph::Lowlink ll(to, e);
	ll.build();
	vector<int> dp(v, INF);
	dp[s] = 0;
	queue<int>q;
	q.push(s);
	while (!q.empty()) {
		auto v = q.front();
		q.pop();
		for (auto[nv, idx] : to[v]) {
			if (chmin(dp[nv], dp[v] + 1))q.push(nv);
		}
	}
	int ans = dp[g];
	if (ans == INF) {
		cout << -1 << endl;
		return 0;
	}
	rep(i, e) {
		if (ll.query(i, s, g) && ll.bridge[i])ans--;
	}
	cout << ans << endl;
	return 0;
}