結果

問題 No.1254 補強への架け橋
コンテスト
ユーザー leeh18
提出日時 2022-08-28 02:48:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 1,306 bytes
コンパイル時間 2,129 ms
コンパイル使用メモリ 205,360 KB
最終ジャッジ日時 2025-01-31 06:36:19
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// #pragma GCC optimize("O3")
// #ifndef ONLINE_JUDGE
// #define _GLIBCXX_DEBUG
// #endif
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int N;
    cin >> N;
    vector<vector<pair<int, int>>> adj(N);
    for (auto i = 0; i < N; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    vector<char> visited(N);
    vector<int> tin(N, -1), low(N, -1);
    int timer = 0;
    vector<char> color(N);
    auto dfs = [&](auto self, int u, int par) -> void {
        visited[u] = true;
        tin[u] = low[u] = timer++;
        for (auto [v, i] : adj[u]) if (v != par){
            if (visited[v]) {
                low[u] = min(low[u], tin[v]);
            } else {
                self(self, v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > tin[u]) {
                    color[i] = 1;
                }
            }
        }
    };
    dfs(dfs, 0, 0);
    cout << count_if(begin(color), end(color), [](auto x) {return !x;}) << '\n';
    for (auto i = 0; i < N; ++i) {
        if (!color[i]) {
            cout << i + 1 << ' ';
        }
    }
}

auto main() -> signed {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    solve();
    return 0;
}
0