結果
問題 | No.1254 補強への架け橋 |
ユーザー |
![]() |
提出日時 | 2024-01-08 20:35:14 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 110 ms / 2,000 ms |
コード長 | 2,389 bytes |
コンパイル時間 | 1,370 ms |
コンパイル使用メモリ | 133,652 KB |
実行使用メモリ | 26,328 KB |
最終ジャッジ日時 | 2024-09-27 19:41:16 |
合計ジャッジ時間 | 12,332 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
#include <algorithm>#include <iostream>#include <vector>using namespace std;class LowLink {public:std::vector<int> ord;std::vector<int> low;std::vector <std::pair<int, int>> bridge;std::vector<int> joint_list;std::vector<bool> joint_or_not;std::vector <std::vector<int>> G;LowLink(int N) {ord.resize(N, -1);low.resize(N, -1);G.resize(N, vector<int>());k = 0;joint_or_not.resize(N, false);}LowLink(const std::vector <std::vector<int>> &G) {ord.resize(G.size(), -1);low.resize(G.size(), -1);this->G = G;k = 0;joint_or_not.resize(G.size(), false);build();}void build() {for (int v = 0; v < (int) G.size(); ++v) {if (ord[v] == -1) {dfs(v);}}}void add_edge(int u, int v) {G[u].push_back(v);G[v].push_back(u);}bool is_bridge(int u, int v) {if (ord[u] > ord[v]) {std::swap(u, v);}return ord[u] < low[v];}bool is_joint(int v) {return std::find(joint_list.begin(), joint_list.end(), v) != joint_list.end();}private:int k;void dfs(int v, int parent = -1) {ord[v] = k++;low[v] = ord[v];bool is_joint = false;int cnt = 0;for (int u : G[v]) {if (u == parent) {continue;}if (ord[u] == -1) {++cnt;dfs(u, v);low[v] = std::min(low[v], low[u]);if (parent != -1 && ord[v] <= low[u]) {is_joint = true;}if (ord[v] < low[u]) {bridge.emplace_back(std::minmax(u, v));}} else {low[v] = std::min(low[v], ord[u]);}}if (parent == -1 && cnt > 1) {is_joint = true;}joint_or_not[v] = is_joint;if (is_joint) {joint_list.push_back(v);}}};int main() {std::cin.tie(0)->sync_with_stdio(0);int N;cin >> N;vector <vector<int>> G(N + 1);vector<tuple<int, int, int>> edges;for (int i = 1; i <= N; ++i) {int a, b;cin >> a >> b;G[a].push_back(b);G[b].push_back(a);edges.emplace_back(a, b, i);}LowLink lowlink(G);vector<int> ans;for (auto e : edges) {if (not lowlink.is_bridge(get<0>(e), get<1>(e))) {ans.push_back(get<2>(e));}}cout << ans.size() << endl;for (int a : ans) {cout << a << " ";}cout << endl;return 0;}