#1157136 (C++23) No.1983 [Cherry 4th Tune C] 南の島のマーメイド

• 問題: No.1983 [Cherry 4th Tune C] 南の島のマーメイド
• ユーザー: kwm_t
• 提出日時: 2026-04-12 15:25:07
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 275 ms / 4,000 ms
• コード長: 4,154 bytes
• コンパイル時間: 5,460 ms
• コンパイル使用メモリ: 388,028 KB
• 実行使用メモリ: 74,796 KB
• 最終ジャッジ日時: 2026-04-12 15:25:24
• 合計ジャッジ時間: 16,560 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
other	AC * 41

ソースコード

#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:
 *   - https://yukicoder.me/submissions/1157134
 */
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 n, m, q; cin >> n >> m >> q;
	vector g(n, vector<P>());
	vector<P>e(m);
	rep(i, m) {
		int u, v; cin >> u >> v;
		u--, v--;
		g[u].emplace_back(v, i);
		g[v].emplace_back(u, i);
		e[i] = { u,v };
	}
	kwm_t::graph::Lowlink lowlink(g, m);
	lowlink.build();
	auto bridge = lowlink.bridge;
	dsu uf(n);
	rep(i, m)if (bridge[i] != -1) {
		uf.merge(e[i].first, e[i].second);
	}
	rep(i, q) {
		int x, y; cin >> x >> y; x--, y--;
		if (uf.same(x, y))cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}