test/aoj0377.test.cpp

View this file on GitHub
Last update: 2021-06-21 15:24:20+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0377

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0377"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#include "../graph/twoedgeconnectedcomponents.cpp"

#include "../datastructure/unionfind.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    TwoEdgeConnectedComponents G(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        G.add_edge(a, b);
    }
    int k = G.build();
    vector<vector<int>> g(k);
    vector<int> v(k);
    UnionFind uf(k);
    for (int i = 0; i < k; ++i) v[i] = G.out[i].size();
    for (int i = 0; i < n; ++i) {
        for (auto &&j : G.G[i]) {
            if(G.is_bridge(i, j)){
                g[G.bridge[i]].emplace_back(G.bridge[j]);
                uf.unite(G.bridge[i], G.bridge[j]);
            }
        }
    }
    int ans = 0;
    vector<int> dp1(v), dp2(k);
    auto dfs = [&](int x, int par, auto &&f) -> void{
        for (auto &&y : g[x]) {
            if(y == par) continue;
            f(y, x, f);
            dp2[x] += max(dp1[y], dp2[y]);
            dp1[x] += dp2[y];
        }
    };
    for (int i = 0; i < k; ++i) {
        if(uf.root(i) == i) {
            dfs(i, -1, dfs);
            ans += max(dp1[i], dp2[i]);
        }
    }
    cout << ans << "\n";
    return 0;
}

#line 1 "test/aoj0377.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0377"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#line 1 "graph/twoedgeconnectedcomponents.cpp"
class TwoEdgeConnectedComponents {
    void dfs(int i, int &pos){
        ord[i] = low[i] = pos++;
        int mul = 0;
        for (auto &&j : G[i]) {
            if(j == par[i] && !mul){
                mul = 1;
                continue;
            }
            if(~ord[j]){
                low[i] = min(low[i], ord[j]);
                continue;
            }
            par[j] = i;
            dfs(j, pos);
            size[i] += size[j];
            low[i] = min(low[i], low[j]);
        }
    }

    void dfs2(int i){
        out[bridge[i]].emplace_back(i);
        for (auto &&j : G[i]) {
            if(~bridge[j] || is_bridge(i, j)) continue;
            bridge[j] = bridge[i];
            dfs2(j);
        }
    }
public:
    vector<int> ord, low, par, bridge, size;
    vector<vector<int>> G, out;
    explicit TwoEdgeConnectedComponents(int n): ord(n, -1), low(n), par(n, -1), bridge(n, -1), size(n, 1), G(n){}

    inline bool is_bridge(int i, int j){
        if(ord[i] > ord[j]) swap(i, j);
        return ord[i] < low[j];
    }

    void add_edge(int u, int v){
        if(u != v){
            G[u].emplace_back(v);
            G[v].emplace_back(u);
        }
    }

    int build(){
        int n = G.size(), pos = 0;
        for (int i = 0; i < n; ++i) {
            if(ord[i] < 0) dfs(i, pos);
        }
        int k = 0;
        for (int i = 0; i < n; ++i) {
            if(!~bridge[i]){
                bridge[i] = k++;
                out.emplace_back();
                dfs2(i);
            }
        }
        return k;
    }
};
#line 21 "test/aoj0377.test.cpp"

#line 1 "datastructure/unionfind.cpp"
class UnionFind {
    int n;
    vector<int> uni;
    int forest_size;
public:
    explicit UnionFind(int n) : n(n), uni(static_cast<uint>(n), -1), forest_size(n) {};

    int root(int a){
        if (uni[a] < 0) return a;
        else return (uni[a] = root(uni[a]));
    }

    bool unite(int a, int b) {
        a = root(a);
        b = root(b);
        if(a == b) return false;
        if(uni[a] > uni[b]) swap(a, b);
        uni[a] += uni[b];
        uni[b] = a;
        forest_size--;
        return true;
    }
    int size(){ return forest_size; }
    int size(int i){ return -uni[root(i)]; }
    bool same(int a, int b) { return root(a) == root(b); }
};

/**
 * @brief UnionFind(素集合データ構造)
 * @docs _md/unionfind.md
 */
#line 23 "test/aoj0377.test.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    TwoEdgeConnectedComponents G(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        G.add_edge(a, b);
    }
    int k = G.build();
    vector<vector<int>> g(k);
    vector<int> v(k);
    UnionFind uf(k);
    for (int i = 0; i < k; ++i) v[i] = G.out[i].size();
    for (int i = 0; i < n; ++i) {
        for (auto &&j : G.G[i]) {
            if(G.is_bridge(i, j)){
                g[G.bridge[i]].emplace_back(G.bridge[j]);
                uf.unite(G.bridge[i], G.bridge[j]);
            }
        }
    }
    int ans = 0;
    vector<int> dp1(v), dp2(k);
    auto dfs = [&](int x, int par, auto &&f) -> void{
        for (auto &&y : g[x]) {
            if(y == par) continue;
            f(y, x, f);
            dp2[x] += max(dp1[y], dp2[y]);
            dp1[x] += dp2[y];
        }
    };
    for (int i = 0; i < k; ++i) {
        if(uf.root(i) == i) {
            dfs(i, -1, dfs);
            ans += max(dp1[i], dp2[i]);
        }
    }
    cout << ans << "\n";
    return 0;
}