test/graph/Articulation_Points.test.cpp

View this file on GitHub
Last update: 2023-11-04 02:52:26+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A

Depends on

Code

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

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

using namespace lib;

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector g(n, std::vector<int>());
    rep(i, 0, m) {
        int s, t;
        std::cin >> s >> t;
        g[s].emplace_back(t);
        g[t].emplace_back(s);
    }
    low_link lwlk(g);
    auto articulation = lwlk.articulation();
    std::sort(all(articulation));
    for (auto v : articulation) {
        std::cout << v << '\n';
    }
}

#line 1 "test/graph/Articulation_Points.test.cpp"
#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 3 "graph/low_link.hpp"

namespace lib {

struct low_link {
    low_link(const std::vector<std::vector<int>> &g) : n(g.size()), ord(n, -1), low(n), par(n,-1) {
        int k = 0;
        auto dfs = [&](auto &&self, int v) -> void {
            low[v] = ord[v] = k++;
            int cnt = 0;
            bool is_arti = false, is_second = false;
            for(auto nv: g[v]) {
                if(ord[nv] == -1) {
                    cnt++;
                    par[nv] = v;
                    self(self, nv);
                    chmin(low[v], low[nv]);
                    is_arti |= par[v] != -1 && low[nv] >= ord[v];
                    if(ord[v] < low[nv]) {
                        _bridge.emplace_back(std::minmax(v, nv));
                    }
                }
                else if(nv != par[v] || is_second) {
                    chmin(low[v], ord[nv]);
                }
                else {
                    is_second = true;
                }
            }
            is_arti |= par[v] == -1 && cnt > 1;
            if(is_arti) _articulation.emplace_back(v);
        };
        dfs(dfs, 0);
    }

    bool is_bridge(int u, int v) {
        if(par[v] != u) std::swap(u, v);
        if(par[v] != u) return false;
        return ord[u] < low[v];
    }

    std::vector<std::pair<int,int>> bridge() {
        return _bridge;
    }

    std::vector<int> articulation() {
        return _articulation;
    }
    
    int n;
    std::vector<int> ord, low, par, _articulation;
    std::vector<std::pair<int,int>> _bridge;
};

}
#line 6 "test/graph/Articulation_Points.test.cpp"

using namespace lib;

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector g(n, std::vector<int>());
    rep(i, 0, m) {
        int s, t;
        std::cin >> s >> t;
        g[s].emplace_back(t);
        g[t].emplace_back(s);
    }
    low_link lwlk(g);
    auto articulation = lwlk.articulation();
    std::sort(all(articulation));
    for (auto v : articulation) {
        std::cout << v << '\n';
    }
}