Test/AOJ/GRL_3_B.test.cpp

View this file on GitHub
Last update: 2025-06-09 10:00:52+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_B

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_B"

#include "../../Src/Graph/Components/Lowlink.hpp"

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

using namespace zawa;

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n, m; 
    std::cin >> n >> m;
    Lowlink g(n);
    for (int _{} ; _ < m ; _++) {
        int s, t; 
        std::cin >> s >> t;
        g.addEdge(s, t);
    }
    auto info{g.build()};
    std::vector<std::pair<int, int>> ans;
    for (int i{} ; i < m ; i++) {
        if (info.isBridge(i)) {
            auto [u, v]{g.edge(i)};
            ans.emplace_back(std::min(u, v), std::max(u, v));
        }
    }
    std::sort(ans.begin(), ans.end());
    for (auto [u, v] : ans) {
        std::cout << u << ' ' << v << '\n';
    }
}

#line 1 "Test/AOJ/GRL_3_B.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_B"

#line 2 "Src/Graph/Components/Lowlink.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Graph/Components/Lowlink.hpp"

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

class Lowlink {
public:

    using V = usize;

    using ID = usize;

private:

    class LowlinkResponse {
    public:

        LowlinkResponse() = default;

        LowlinkResponse(std::vector<u32>&& articulation, std::vector<bool>&& bridge)
            : articulation_{std::move(articulation)}, bridge_{std::move(bridge)} {}

        inline bool isArticulation(V v) const {
            assert(v < articulation_.size());
            return articulation_[v] > 1u;
        }

        inline u32 cut(V v) const {
            assert(v < articulation_.size());
            return articulation_[v];
        }

        inline bool isBridge(ID i) const {
            assert(i < bridge_.size());
            return bridge_[i];
        }

    private:

        std::vector<u32> articulation_;

        std::vector<bool> bridge_;

    };

    static constexpr usize INVALID{static_cast<usize>(-1)};

    usize n_{}, m_{};

    std::vector<std::vector<std::pair<V, ID>>> g_;

    std::vector<std::pair<V, V>> e_;

    void dfs(V v, V p, u32& t, std::vector<u32>& articulation, 
            std::vector<bool>& bridge, std::vector<usize>& in, std::vector<usize>& low) const {
        low[v] = in[v] = t++;
        u32 deg{}; 
        for (const auto& [x, i] : g_[v]) {
            if (in[x] == INVALID) {
                deg++;
                dfs(x, v, t, articulation, bridge, in, low);
                low[v] = std::min(low[v], low[x]);
                if (p != INVALID and low[x] >= in[v]) {
                    articulation[v]++;
                }
                if (low[x] > in[v]) {
                    bridge[i] = true;
                }
            }
            else if (x != p) {
                low[v] = std::min(low[v], in[x]);
            }
        }
        if (p == INVALID) {
            articulation[v] = deg;
        }
    }

public:

    constexpr usize size() const noexcept {
        return n_;
    }

    constexpr usize edgeSize() const noexcept {
        return m_;
    }

    Lowlink() = default;

    explicit Lowlink(usize n) 
        : n_{n}, m_{}, g_(n) {
        g_.shrink_to_fit();
    }
    
    ID addEdge(V u, V v) {
        ID res{m_++};
        e_.emplace_back(u, v);
        g_[u].emplace_back(v, res);
        g_[v].emplace_back(u, res);
        return res;
    }

    const std::vector<std::pair<V, ID>>& operator[](V v) const noexcept {
        assert(v < size());
        return g_[v];
    }
    const std::pair<V, V>& edge(ID i) const noexcept {
        assert(i < edgeSize());
        return e_[i];
    }

    LowlinkResponse build() const {
        u32 t{};
        std::vector<u32> articulation(size(), 1u);
        std::vector<usize> in(size(), INVALID), low(size());
        std::vector<bool> bridge(edgeSize());
        for (u32 v{} ; v < size() ; v++) if (in[v] == INVALID) {
            dfs(v, INVALID, t, articulation, bridge, in, low);
        }
        return LowlinkResponse{ std::move(articulation), std::move(bridge) };
    }

};

} // namespace zawa
#line 4 "Test/AOJ/GRL_3_B.test.cpp"

#line 6 "Test/AOJ/GRL_3_B.test.cpp"
#include <iostream>
#line 9 "Test/AOJ/GRL_3_B.test.cpp"

using namespace zawa;

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n, m; 
    std::cin >> n >> m;
    Lowlink g(n);
    for (int _{} ; _ < m ; _++) {
        int s, t; 
        std::cin >> s >> t;
        g.addEdge(s, t);
    }
    auto info{g.build()};
    std::vector<std::pair<int, int>> ans;
    for (int i{} ; i < m ; i++) {
        if (info.isBridge(i)) {
            auto [u, v]{g.edge(i)};
            ans.emplace_back(std::min(u, v), std::max(u, v));
        }
    }
    std::sort(ans.begin(), ans.end());
    for (auto [u, v] : ans) {
        std::cout << u << ' ' << v << '\n';
    }
}