結果
問題 | No.1254 補強への架け橋 |
ユーザー |
![]() |
提出日時 | 2020-11-11 04:03:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 338 ms / 2,000 ms |
コード長 | 2,692 bytes |
コンパイル時間 | 2,731 ms |
コンパイル使用メモリ | 224,540 KB |
最終ジャッジ日時 | 2025-01-15 22:04:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename T> class Edge { public: std::size_t from; std::size_t to; T cost; Edge(const std::size_t from, const std::size_t to, const T cost = 0) : from(from), to(to), cost(cost){}; bool operator<(const Edge<T> &rhs) const { return cost < rhs.cost; } bool operator>(const Edge<T> &rhs) const { return cost > rhs.cost; } }; template <typename T> class Graph { private: std::vector<std::vector<Edge<T>>> graph; public: explicit Graph(const std::size_t n) : graph(n) {} std::vector<Edge<T>> operator[](const std::size_t i) const { return graph[i]; } std::vector<Edge<T>> &operator[](const std::size_t i) { return graph[i]; } std::size_t size() const { return graph.size(); } void add(const std::size_t u, const std::size_t v, const T c = 0) { graph[u].emplace_back(Edge(u, v, c)); } }; template <typename T> class LowLink { public: const Graph<T> graph; std::vector<bool> used; std::vector<int> ord, low; std::vector<int> aps; std::vector<std::pair<int, int>> bridges; explicit LowLink(const Graph<T> &g) : graph(g), used(g.size(), false), ord(g.size(), 0), low(g.size(), 0) { int k = 0; for (int i = 0; i < (int)g.size(); i++) { if (!used[i]) k = dfs(i, k, -1); } sort(aps.begin(), aps.end()); sort(bridges.begin(), bridges.end()); } int dfs(int id, int k, int par) { used[id] = true; ord[id] = k++; low[id] = ord[id]; bool is_aps = false; int count = 0; for (auto &e : graph[id]) { if (!used[e.to]) { count++; k = dfs(e.to, k, id); low[id] = min(low[id], low[e.to]); if (par != -1 && ord[id] <= low[e.to]) is_aps = true; if (ord[id] < low[e.to]) bridges.emplace_back(make_pair(min(id, (int)e.to), max(id, (int)e.to))); } else if (e.to != par) { low[id] = min(low[id], ord[e.to]); } } if (par == -1 && count >= 2) is_aps = true; if (is_aps) aps.emplace_back(id); return k; }; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; Graph<int> G(N); map<pair<int, int>, int> mp; for (int i = 0; i < N; i++) { int a, b; cin >> a >> b; a--, b--; G.add(a, b); G.add(b, a); mp[make_pair(a, b)] = i; mp[make_pair(b, a)] = i; } LowLink ll(G); set<int> st; for (auto b : ll.bridges) { st.insert(mp[b]); } cout << N - st.size() << '\n'; vector<int> res; for (int i = 0; i < N; i++) { if (st.find(i) == st.end()) res.emplace_back(i); } for (const auto &e : res) { cout << e + 1 << (&e == &res.back() ? '\n' : ' '); } return 0; }