#596823 (C++17) No.1254 補強への架け橋

• 問題: No.1254 補強への架け橋
• ユーザー: outline
• 提出日時: 2020-12-23 18:13:36
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 91 ms / 2,000 ms
• コード長: 3,360 bytes
• コンパイル時間: 1,328 ms
• コンパイル使用メモリ: 147,988 KB
• 実行使用メモリ: 22,248 KB
• 最終ジャッジ日時: 2023-10-21 15:14:41
• 合計ジャッジ時間: 12,404 ms
• ジャッジサーバーID （参考情報）: judge12 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	1 ms; 4,348 KB
testcase_04	AC	1 ms; 4,348 KB
testcase_05	AC	1 ms; 4,348 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	2 ms; 4,348 KB
testcase_08	AC	2 ms; 4,348 KB
testcase_09	AC	1 ms; 4,348 KB
testcase_10	AC	1 ms; 4,348 KB
testcase_11	AC	2 ms; 4,348 KB
testcase_12	AC	2 ms; 4,348 KB
testcase_13	AC	2 ms; 4,348 KB
testcase_14	AC	2 ms; 4,348 KB
testcase_15	AC	2 ms; 4,348 KB
testcase_16	AC	1 ms; 4,348 KB
testcase_17	AC	1 ms; 4,348 KB
testcase_18	AC	2 ms; 4,348 KB
testcase_19	AC	2 ms; 4,348 KB
testcase_20	AC	2 ms; 4,348 KB
testcase_21	AC	1 ms; 4,348 KB
testcase_22	AC	2 ms; 4,348 KB
testcase_23	AC	2 ms; 4,348 KB
testcase_24	AC	2 ms; 4,348 KB
testcase_25	AC	2 ms; 4,348 KB
testcase_26	AC	2 ms; 4,348 KB
testcase_27	AC	1 ms; 4,348 KB
testcase_28	AC	2 ms; 4,348 KB
testcase_29	AC	1 ms; 4,348 KB
testcase_30	AC	2 ms; 4,348 KB
testcase_31	AC	2 ms; 4,348 KB
testcase_32	AC	2 ms; 4,348 KB
testcase_33	AC	1 ms; 4,348 KB
testcase_34	AC	1 ms; 4,348 KB
testcase_35	AC	2 ms; 4,348 KB
testcase_36	AC	1 ms; 4,348 KB
testcase_37	AC	1 ms; 4,348 KB
testcase_38	AC	1 ms; 4,348 KB
testcase_39	AC	2 ms; 4,348 KB
testcase_40	AC	1 ms; 4,348 KB
testcase_41	AC	1 ms; 4,348 KB
testcase_42	AC	2 ms; 4,348 KB
testcase_43	AC	2 ms; 4,348 KB
testcase_44	AC	2 ms; 4,348 KB
testcase_45	AC	2 ms; 4,348 KB
testcase_46	AC	2 ms; 4,348 KB
testcase_47	AC	2 ms; 4,348 KB
testcase_48	AC	2 ms; 4,348 KB
testcase_49	AC	1 ms; 4,348 KB
testcase_50	AC	2 ms; 4,348 KB
testcase_51	AC	2 ms; 4,348 KB
testcase_52	AC	3 ms; 4,348 KB
testcase_53	AC	2 ms; 4,348 KB
testcase_54	AC	2 ms; 4,348 KB
testcase_55	AC	2 ms; 4,348 KB
testcase_56	AC	2 ms; 4,348 KB
testcase_57	AC	2 ms; 4,348 KB
testcase_58	AC	2 ms; 4,348 KB
testcase_59	AC	2 ms; 4,348 KB
testcase_60	AC	2 ms; 4,348 KB
testcase_61	AC	2 ms; 4,348 KB
testcase_62	AC	2 ms; 4,348 KB
testcase_63	AC	9 ms; 4,676 KB
testcase_64	AC	3 ms; 4,348 KB
testcase_65	AC	6 ms; 4,348 KB
testcase_66	AC	5 ms; 4,348 KB
testcase_67	AC	3 ms; 4,348 KB
testcase_68	AC	5 ms; 4,348 KB
testcase_69	AC	6 ms; 4,428 KB
testcase_70	AC	3 ms; 4,348 KB
testcase_71	AC	3 ms; 4,348 KB
testcase_72	AC	6 ms; 4,448 KB
testcase_73	AC	3 ms; 4,348 KB
testcase_74	AC	7 ms; 4,400 KB
testcase_75	AC	5 ms; 4,348 KB
testcase_76	AC	2 ms; 4,348 KB
testcase_77	AC	4 ms; 4,348 KB
testcase_78	AC	7 ms; 4,540 KB
testcase_79	AC	8 ms; 4,580 KB
testcase_80	AC	6 ms; 4,500 KB
testcase_81	AC	8 ms; 4,584 KB
testcase_82	AC	7 ms; 4,580 KB
testcase_83	AC	90 ms; 15,572 KB
testcase_84	AC	87 ms; 15,352 KB
testcase_85	AC	50 ms; 10,764 KB
testcase_86	AC	74 ms; 13,800 KB
testcase_87	AC	81 ms; 14,608 KB
testcase_88	AC	13 ms; 5,184 KB
testcase_89	AC	87 ms; 15,496 KB
testcase_90	AC	53 ms; 11,260 KB
testcase_91	AC	41 ms; 9,476 KB
testcase_92	AC	21 ms; 6,616 KB
testcase_93	AC	73 ms; 13,092 KB
testcase_94	AC	62 ms; 12,304 KB
testcase_95	AC	64 ms; 12,156 KB
testcase_96	AC	91 ms; 15,028 KB
testcase_97	AC	35 ms; 8,800 KB
testcase_98	AC	85 ms; 14,968 KB
testcase_99	AC	48 ms; 10,536 KB
testcase_100	AC	90 ms; 15,964 KB
testcase_101	AC	19 ms; 6,404 KB
testcase_102	AC	10 ms; 4,944 KB
testcase_103	AC	22 ms; 6,580 KB
testcase_104	AC	29 ms; 7,748 KB
testcase_105	AC	68 ms; 13,100 KB
testcase_106	AC	38 ms; 9,032 KB
testcase_107	AC	86 ms; 15,504 KB
testcase_108	AC	90 ms; 15,408 KB
testcase_109	AC	70 ms; 13,036 KB
testcase_110	AC	61 ms; 12,236 KB
testcase_111	AC	66 ms; 12,860 KB
testcase_112	AC	28 ms; 7,672 KB
testcase_113	AC	60 ms; 11,972 KB
testcase_114	AC	38 ms; 8,872 KB
testcase_115	AC	13 ms; 5,372 KB
testcase_116	AC	42 ms; 9,964 KB
testcase_117	AC	28 ms; 7,632 KB
testcase_118	AC	84 ms; 14,840 KB
testcase_119	AC	46 ms; 10,276 KB
testcase_120	AC	80 ms; 14,492 KB
testcase_121	AC	23 ms; 6,928 KB
testcase_122	AC	42 ms; 9,680 KB
testcase_123	AC	2 ms; 4,348 KB
testcase_124	AC	55 ms; 22,248 KB
testcase_125	AC	52 ms; 22,248 KB

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <array>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <cstring>
#include <unordered_map>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
// constexpr int mod = 1000000007;
constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template<typename G>
struct LowLink{
    const G& g;
    vector<int> visited, order, low;
    vector<int> articulation;           // 関節点
    vector<pair<int, int>> bridge;      // 橋 (order[from] < low[to])
    int LinkSize = 0;       // 連結成分の個数

    LowLink(const G &g) : g(g) {}

    int dfs(int from, int k, int par = -1){
        visited[from] = true;
        order[from] = k++;
        low[from] = order[from];
        bool is_articulation = false;
        int cnt = 0;
        for(auto &to : g[from]){
            if(!visited[to]){
                ++cnt;
                k = dfs(to, k, from);
                low[from] = min(low[from], low[to]);
                // 頂点 from がDFS木の根以外であるときの関節点となる条件
                is_articulation |= ~par && low[to] >= order[from];
                // (from, to) が条件を満たせば、橋に追加
                if(order[from] < low[to]) bridge.emplace_back(minmax(from, (int)to));
            }
            else if(to != par){
                low[from] = min(low[from], order[to]);
            }
        }
        // 頂点 from がDFS木の根であるときの関節点となる条件
        is_articulation |= par == -1 && cnt > 1;
        if(is_articulation) articulation.push_back(from);
        return k;
    }

    virtual void build(){
        visited.assign(g.size(), 0);
        order.assign(g.size(), 0);
        low.assign(g.size(), 0);
        int k = 0;
        for(int i = 0; i < g.size(); ++i){
            if(!visited[i]){
                k = dfs(i, k);
                ++LinkSize;
            }
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> a(N), b(N);
    vector<vector<int>> graph(N);
    for(int i = 0; i < N; ++i){
        cin >> a[i] >> b[i];
        --a[i], --b[i];
        graph[a[i]].emplace_back(b[i]);
        graph[b[i]].emplace_back(a[i]);
    }

    LowLink<vector<vector<int>>> g(graph);
    g.build();
    set<P> bridge;
    for(auto [u, v] : g.bridge){
        bridge.emplace(minmax(u, v));
    }

    vector<int> ans;
    for(int i = 0; i < N; ++i){
        if(bridge.find(minmax(a[i], b[i])) != bridge.end()) continue;
        ans.emplace_back(i + 1);
    }

    int n = ans.size();
    cout << n << '\n';
    for(int i = 0; i < n; ++i){
        cout << ans[i];
        cout << ((i == n - 1) ? '\n' : ' ');
    }

    return 0;
}