test/aoj/GRL_3_B.test.cpp

• View this file on GitHub
• Last update: 2025-07-07 14:21:50+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B

Depends on

• Low Link (graph/low_link.hpp)

Required by

• test/utility/next_combination.test.cpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"

#include <bits/stdc++.h>
using namespace std;

#include "../../graph/low_link.hpp"

int main() {
    int N, M;
    cin >> N >> M;
    LowLink lo(N);
    vector<pair<int, int>> edge(M);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        edge[i] = make_pair(min(u, v), max(u, v));
        lo.add_edge(u, v);
    }

    lo.build();

    vector<pair<int, int>> ans;
    for (auto [u, v] : edge) {
        if (lo.is_bridge(u, v)) {
            ans.push_back(make_pair(u, v));
        }
    }

    sort(ans.begin(), ans.end());

    for (auto [u, v] : ans) {
        cout << u << ' ' << v << endl;
    }
}

#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 <bits/stdc++.h>
using namespace std;

#line 2 "graph/low_link.hpp"

/**
 * @brief Low Link
 */
class LowLink {
  private:
    bool init;
    int n, comp;
    vector<vector<int>> g;
    vector<bool> seen;
    vector<int> ord, low, art;
    set<pair<int, int>> bri;

    void dfs(int v, int p, int& i) {
        seen[v] = true;
        ord[v] = low[v] = i++;
        for (const int& nv : g[v]) {
            if (seen[nv]) {
                if (nv != p) {
                    low[v] = min(low[v], ord[nv]);
                }
            } else {
                dfs(nv, v, i);
                low[v] = min(low[v], low[nv]);
                if (ord[v] <= low[nv])
                    art[v]++;
                if (ord[v] < low[nv])
                    bri.insert(make_pair(min(v, nv), max(v, nv)));
            }
        }
        if (p == -1)
            art[v]--;
    }

  public:
    LowLink() {}
    LowLink(const int _n)
        : init(false), n(_n), comp(0), g(_n), seen(_n), ord(_n), low(_n), art(_n) {}

    void add_edge(int u, int v) {
        assert(!init);

        g[u].push_back(v);
        g[v].push_back(u);
    }

    void build() {
        assert(!init);
        init = true;

        for (int v = 0; v < n; v++)
            if (!seen[v]) {
                comp++;
                int i{};
                dfs(v, -1, i);
            }
    }

    int component() const {
        assert(init);

        return comp;
    }

    int get_art(int v) const {
        assert(init);

        return art[v];
    }

    bool is_art(int v) const {
        assert(init);

        return 0 < get_art(v);
    }

    bool is_bridge(int u, int v) const {
        assert(init);

        return bri.count(make_pair(min(u, v), max(u, v)));
    }
};
#line 7 "test/aoj/GRL_3_B.test.cpp"

int main() {
    int N, M;
    cin >> N >> M;
    LowLink lo(N);
    vector<pair<int, int>> edge(M);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        edge[i] = make_pair(min(u, v), max(u, v));
        lo.add_edge(u, v);
    }

    lo.build();

    vector<pair<int, int>> ans;
    for (auto [u, v] : edge) {
        if (lo.is_bridge(u, v)) {
            ans.push_back(make_pair(u, v));
        }
    }

    sort(ans.begin(), ans.end());

    for (auto [u, v] : ans) {
        cout << u << ' ' << v << endl;
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00.in	AC	4 ms	4 MB
g++	00_small_01.in	AC	3 ms	4 MB
g++	00_small_02.in	AC	3 ms	4 MB
g++	00_small_03.in	AC	3 ms	4 MB
g++	00_small_04.in	AC	3 ms	4 MB
g++	00_small_05.in	AC	3 ms	4 MB
g++	01_critical_00.in	AC	3 ms	4 MB
g++	01_critical_01.in	AC	3 ms	4 MB
g++	01_critical_02.in	AC	3 ms	4 MB
g++	01_critical_03.in	AC	3 ms	4 MB
g++	01_critical_04.in	AC	3 ms	4 MB
g++	01_critical_05.in	AC	3 ms	4 MB
g++	01_critical_06.in	AC	3 ms	4 MB
g++	01_critical_07.in	AC	3 ms	3 MB
g++	01_critical_08.in	AC	3 ms	4 MB
g++	01_critical_09.in	AC	3 ms	4 MB
g++	01_critical_10.in	AC	3 ms	4 MB
g++	01_critical_11.in	AC	3 ms	4 MB
g++	01_critical_12.in	AC	3 ms	4 MB
g++	02_grid_00.in	AC	3 ms	4 MB
g++	02_grid_01.in	AC	3 ms	4 MB
g++	02_grid_02.in	AC	3 ms	3 MB
g++	03_rand_00.in	AC	3 ms	4 MB
g++	03_rand_01.in	AC	3 ms	4 MB
g++	03_rand_02.in	AC	3 ms	4 MB
g++	03_rand_03.in	AC	3 ms	4 MB
g++	03_rand_04.in	AC	3 ms	4 MB
g++	03_rand_05.in	AC	3 ms	3 MB
g++	03_rand_06.in	AC	3 ms	3 MB
g++	03_rand_07.in	AC	3 ms	4 MB
g++	03_rand_08.in	AC	4 ms	4 MB
g++	03_rand_09.in	AC	4 ms	4 MB
g++	03_rand_10.in	AC	5 ms	4 MB
g++	03_rand_11.in	AC	6 ms	4 MB
g++	04_linear_00.in	AC	4 ms	4 MB
g++	04_linear_01.in	AC	4 ms	4 MB
g++	04_linear_02.in	AC	8 ms	5 MB
g++	04_linear_03.in	AC	9 ms	5 MB
g++	05_maximum_00.in	AC	19 ms	5 MB
g++	05_maximum_01.in	AC	25 ms	6 MB

Back to top page