結果

問題 No.1254 補強への架け橋
ユーザー siman
提出日時 2024-01-08 20:19:41
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 103 ms / 2,000 ms
コード長 2,123 bytes
コンパイル時間 1,612 ms
コンパイル使用メモリ 133,184 KB
実行使用メモリ 26,320 KB
最終ジャッジ日時 2024-09-27 19:40:43
合計ジャッジ時間 12,566 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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(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);
for (int v = 0; v < (int) G.size(); ++v) {
if (ord[v] == -1) {
dfs(v);
}
}
}
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0