Test/Aizu Online Judge/GRL/GRL_3_B.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 01:03:27+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_B

Depends on

• LowLink関連 (関節点, 橋) (Graph/lowlink.hpp)

Code

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

#include <bits/stdc++.h>

#include "Graph/lowlink.hpp"

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, u, v;
    cin >> n >> m;
    vector<vector<int>> g(n);
    while(m--){
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    auto ans = lowlink_graph(g).bridge;
    sort(ans.begin(), ans.end());
    for(auto &&[u, v] : ans) cout << u << ' ' << v << '\n';
}

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

#include <bits/stdc++.h>

#line 1 "Graph/lowlink.hpp"
struct lowlink_graph{
    int N;
    std::vector<std::vector<int>>& g;
    std::vector<bool> used;
    std::vector<int> order, low, art_point;
    std::vector<std::pair<int,int>> bridge;
    lowlink_graph(std::vector<std::vector<int>> &G) 
            : N(G.size()), g(G), used(N), order(N), low(N) {
        int timer = 0;
        for(int v = 0; v < N; v++){
            if(!used[v]) dfs_lowlink(v, -1, timer);
        }
    }
    void dfs_lowlink(int v, int par, int &timer){
        used[v] = true;
        low[v] = order[v] = timer++;
        bool is_art_point = false;
        int cnt = 0;
        for(auto &u : g[v]){
            if(!used[u]){
                cnt++;
                dfs_lowlink(u, v, timer);
                low[v] = std::min(low[v], low[u]);
                is_art_point |= ~par && low[u] >= order[v];
                if(order[v] < low[u]) bridge.emplace_back(std::minmax(v, u));
            }else if(u != par){
                low[v] = std::min(low[v], order[u]);
            }
        }
        is_art_point |= par == -1 && cnt > 1;
        if(is_art_point) art_point.push_back(v);
    }
};
#line 5 "Test/Aizu Online Judge/GRL/GRL_3_B.test.cpp"
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, u, v;
    cin >> n >> m;
    vector<vector<int>> g(n);
    while(m--){
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    auto ans = lowlink_graph(g).bridge;
    sort(ans.begin(), ans.end());
    for(auto &&[u, v] : ans) cout << u << ' ' << v << '\n';
}

Back to top page