test/aoj_grl_3_b.test.cpp

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B

Depends on

• LowLink (graph/lowlink.cpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#include "../graph/lowlink.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    LowLink G(n);
    for (int i = 0; i < m; ++i) {
        int s, t;
        scanf("%d %d", &s, &t);
        G.add_edge(s, t);
    }
    G.build();
    for (auto &&e : G.bridge) {
        printf("%d %d\n", e.first, e.second);
    }
    return 0;
}

#line 1 "test/aoj_grl_3_b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#line 1 "graph/lowlink.cpp"
class LowLink {
    void dfs(int i, int p, int &pos){
        ord[i] = low[i] = pos++;
        int ch = 0, mul = 0;
        bool is_art = false;
        for (auto &&j : G[i]) {
            if(j == p && !mul){
                mul = 1;
                continue;
            }
            if(~ord[j]){
                low[i] = min(low[i], ord[j]);
                continue;
            }
            par[j] = i;
            ch++;
            dfs(j, i, pos);
            low[i] = min(low[i], low[j]);
            if(p != -1 && ord[i] <= low[j]) is_art = true;
            if(ord[i] < low[j]) bridge.emplace_back(min(i, j), max(i, j));
        }
        if(p == -1 && ch > 1) is_art = true;
        cut[i] = is_art;
    }
public:
    vector<int> ord, low, par, articulation;
    vector<pair<int, int>> bridge;
    vector<char> cut;
    vector<vector<int>> G;
    LowLink() = default;
    explicit LowLink(int n): ord(n, -1), low(n), par(n, -1), cut(n), G(n){}

    void add_edge(int u, int v){
        if(u != v){
            G[u].emplace_back(v);
            G[v].emplace_back(u);
        }
    }

    void build(){
        int n = G.size(), pos = 0;
        fill(ord.begin(), ord.end(), -1);
        fill(par.begin(), par.end(), -1);
        fill(cut.begin(), cut.end(), 0);
        articulation.clear();
        bridge.clear();
        for (int i = 0; i < n; ++i) {
            if(!~ord[i]) dfs(i, -1, pos);
        }
        for (int i = 0; i < n; ++i) {
            if(cut[i]) articulation.emplace_back(i);
        }
        sort(bridge.begin(), bridge.end());
    }

    inline bool is_bridge(int i, int j){
        if(ord[i] > ord[j]) swap(i, j);
        return ord[i] < low[j];
    }
};

/**
 * @brief LowLink
 */
#line 21 "test/aoj_grl_3_b.test.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    LowLink G(n);
    for (int i = 0; i < m; ++i) {
        int s, t;
        scanf("%d %d", &s, &t);
        G.add_edge(s, t);
    }
    G.build();
    for (auto &&e : G.bridge) {
        printf("%d %d\n", e.first, e.second);
    }
    return 0;
}

Back to top page