program_contest_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ferin-15/program_contest_library

:heavy_check_mark: test/GRL3A.test.cpp

Back to top page

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A&lang=jp"
#include "../memo/macro.hpp"
#include "../graph/articulation.cpp"

int main() {
    ll n, m;
    cin >> n >> m;
    articulation graph(n);
    REP(i, m) {
        ll s, t;
        cin >> s >> t;
        graph.add_edge(s, t);
    }
    auto ret = graph.build();
    sort(ALL(ret));
    for(auto i: ret) cout << i << "\n";
    cout << flush;
}

#line 1 "test/GRL3A.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A&lang=jp"
#line 1 "memo/macro.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
const ll INF = 1LL<<60;
#line 1 "graph/articulation.cpp"
// BEGIN CUT
class articulation {
private:
    void dfs(ll v, ll p, ll &k, vector<ll> &ret) {
        ord[v] = k++;
        low[v] = ord[v];
        ll cnt = 0;
        bool is_articulation = false;
        for(auto to: g[v]) {
            if(ord[to]==-1) {
                dfs(to, v, k, ret);
                chmin(low[v], low[to]);
                ++cnt;
                is_articulation |= p!=-1 && low[to] >= ord[v]; 
            } else if(to != p) {
                chmin(low[v], ord[to]);
            }
        }
        is_articulation |= p==-1 && cnt>1;
        if(is_articulation) ret.push_back(v);
    }
public:
    vector<vector<ll>> g;
    vector<ll> ord, low, cmp;

    articulation() {}
    articulation(ll n) : g(n), ord(n, -1), low(n) {}

    void add_edge(ll u, ll v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<ll> build() {
        ll k = 0;
        vector<ll> ret;
        REP(i, g.size()) if(ord[i]==-1) dfs(i, -1, k, ret);
        return ret;
    }
};
// END CUT
#line 4 "test/GRL3A.test.cpp"

int main() {
    ll n, m;
    cin >> n >> m;
    articulation graph(n);
    REP(i, m) {
        ll s, t;
        cin >> s >> t;
        graph.add_edge(s, t);
    }
    auto ret = graph.build();
    sort(ALL(ret));
    for(auto i: ret) cout << i << "\n";
    cout << flush;
}

Back to top page