This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2744" #include <cassert> #include <iostream> #include "library/graph/bfs.hpp" #include "library/graph/bfs_complement.hpp" int main() { int n, m; std::cin >> n >> m; std::vector<std::vector<int>> g(n); for (int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; --u, --v; g[u].push_back(v); g[v].push_back(u); } std::vector<int> res = [rec = [](auto rec, const std::vector<std::vector<int>> &g) -> std::vector<int> { const int n = g.size(); if (n == 1) return { 0, 0 }; auto cmps = suisen::BFS{g}.connected_components(); if (cmps.size() == 1) { auto ccmps = suisen::ComplementBFS{g}.connected_components(); assert(ccmps.size() != 1); std::vector<int> pd { 0 }; std::vector<int8_t> in(n); std::vector<int> idx(n); for (const auto &cmp : ccmps) { const int siz = cmp.size(); for (int i = 0; i < siz; ++i) { idx[cmp[i]] = i; } std::vector<std::vector<int>> h(siz); for (int v : cmp) in[v] = true; for (int u : cmp) for (int v : g[u]) if (in[v]) { h[idx[u]].push_back(idx[v]); } for (int v : cmp) in[v] = false; std::vector<int> val = rec(rec, h); const int l = pd.size() - 1, r = val.size() - 1; std::vector<int> dp(l + r + 1); for (int i = 0; i <= l; ++i) { for (int j = 0; j <= r; ++j) { dp[i + j] = std::max(dp[i + j], pd[i] + val[j] + i * (r - j) + (l - i) * j); } } pd.swap(dp); } return pd; } else { std::vector<int> pd{ 0 }; std::vector<int> idx(n); for (const auto &cmp : cmps) { const int siz = cmp.size(); for (int i = 0; i < siz; ++i) idx[cmp[i]] = i; std::vector<std::vector<int>> h(siz); for (int u : cmp) for (int v : g[u]) { h[idx[u]].push_back(idx[v]); } std::vector<int> val = rec(rec, h); const int l = pd.size() - 1, r = val.size() - 1; std::vector<int> dp(l + r + 1); for (int i = 0; i <= l; ++i) { for (int j = 0; j <= r; ++j) { dp[i + j] = std::max(dp[i + j], pd[i] + val[j]); } } pd.swap(dp); } return pd; } }, &g]{ return rec(rec, g); }(); std::cout << *std::max_element(res.begin(), res.end()) << std::endl; }
#line 1 "test/src/graph/bfs_complement/AOJ_2744.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2744" #include <cassert> #include <iostream> #line 1 "library/graph/bfs.hpp" #include <algorithm> #include <cstdint> #include <deque> #include <numeric> #include <utility> #include <vector> namespace suisen { struct BFS { static constexpr int unreachable = -1; BFS(int n = 0) : n(n), g(n) {} template <typename Edges> BFS(int n, const Edges& edges) : BFS(n) { for (const auto& [u, v] : edges) add_edge(u, v); } BFS(const std::vector<std::vector<int>>& g) : n(g.size()), g(g) {} void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } std::vector<int> distance(const std::vector<int>& src) const { std::vector<int> dist(n, unreachable); for (int v : src) dist[v] = 0; std::deque<int> dq(src.begin(), src.end()); while (dq.size()) { int u = dq.front(); dq.pop_front(); for (int v : g[u]) if (dist[v] == unreachable) { dist[v] = dist[u] + 1; dq.push_back(v); } } return dist; } std::vector<int> distance(int s) const { return distance(std::vector<int>{ s }); } std::vector<std::vector<int>> connected_components() const { std::vector<std::vector<int>> res; std::vector<int8_t> vis(n, false); for (int i = 0; i < n; ++i) if (not std::exchange(vis[i], true)) { auto& cmp = res.emplace_back(); std::deque<int> dq{ i }; while (dq.size()) { int u = dq.front(); dq.pop_front(); cmp.push_back(u); for (int v : g[u]) if (not std::exchange(vis[v], true)) { dq.push_back(v); } } } return res; } private: int n; std::vector<std::vector<int>> g; }; } // namespace suisen #line 1 "library/graph/bfs_complement.hpp" #line 10 "library/graph/bfs_complement.hpp" namespace suisen { struct ComplementBFS { static constexpr int unreachable = -1; ComplementBFS(int n = 0) : n(n), g(n) {} template <typename Edges> ComplementBFS(int n, const Edges &edges) : ComplementBFS(n) { for (const auto &[u, v] : edges) add_edge(u, v); } ComplementBFS(const std::vector<std::vector<int>>& g) : n(g.size()), g(g) {} void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } std::vector<int> distance(const std::vector<int>& src) const { std::vector<int> s = [&] { std::vector<int8_t> is_src(n); for (int v : src) is_src[v] = true; std::vector<int> s; for (int i = 0; i < n; ++i) if (not is_src[i]) s.push_back(i); return s; }(); std::vector<int> dist(n, unreachable); for (int v : src) dist[v] = 0; std::vector<int8_t> adj(n); std::deque<int> dq(src.begin(), src.end()); while (dq.size()) { int u = dq.front(); dq.pop_front(); for (int v : g[u]) adj[v] = true; std::size_t nsiz = std::partition(s.begin(), s.end(), [&adj](int v) { return adj[v]; }) - s.begin(); for (; s.size() > nsiz; s.pop_back()) { int v = s.back(); dist[v] = dist[u] + 1, dq.push_back(v); } for (int v : g[u]) adj[v] = false; } return dist; } std::vector<int> distance(int s) const { return distance(std::vector<int>{ s }); } std::vector<std::vector<int>> connected_components() const { std::vector<std::vector<int>> res; std::vector<int8_t> vis(n, false); std::vector<int> s(n); std::iota(s.begin(), s.end(), 0); std::vector<int8_t> adj(n); for (int i = 0; i < n; ++i) if (not vis[i]) { s.erase(std::find(s.begin(), s.end(), i)); auto& cmp = res.emplace_back(); std::deque<int> dq{ i }; while (dq.size()) { int u = dq.front(); dq.pop_front(); cmp.push_back(u); vis[u] = true; for (int v : g[u]) adj[v] = true; auto it = std::partition(s.begin(), s.end(), [&adj](int v) { return adj[v]; }); std::move(it, s.end(), std::back_inserter(dq)); s.erase(it, s.end()); for (int v : g[u]) adj[v] = false; } } return res; } private: int n; std::vector<std::vector<int>> g; }; } // namespace suisen #line 8 "test/src/graph/bfs_complement/AOJ_2744.test.cpp" int main() { int n, m; std::cin >> n >> m; std::vector<std::vector<int>> g(n); for (int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; --u, --v; g[u].push_back(v); g[v].push_back(u); } std::vector<int> res = [rec = [](auto rec, const std::vector<std::vector<int>> &g) -> std::vector<int> { const int n = g.size(); if (n == 1) return { 0, 0 }; auto cmps = suisen::BFS{g}.connected_components(); if (cmps.size() == 1) { auto ccmps = suisen::ComplementBFS{g}.connected_components(); assert(ccmps.size() != 1); std::vector<int> pd { 0 }; std::vector<int8_t> in(n); std::vector<int> idx(n); for (const auto &cmp : ccmps) { const int siz = cmp.size(); for (int i = 0; i < siz; ++i) { idx[cmp[i]] = i; } std::vector<std::vector<int>> h(siz); for (int v : cmp) in[v] = true; for (int u : cmp) for (int v : g[u]) if (in[v]) { h[idx[u]].push_back(idx[v]); } for (int v : cmp) in[v] = false; std::vector<int> val = rec(rec, h); const int l = pd.size() - 1, r = val.size() - 1; std::vector<int> dp(l + r + 1); for (int i = 0; i <= l; ++i) { for (int j = 0; j <= r; ++j) { dp[i + j] = std::max(dp[i + j], pd[i] + val[j] + i * (r - j) + (l - i) * j); } } pd.swap(dp); } return pd; } else { std::vector<int> pd{ 0 }; std::vector<int> idx(n); for (const auto &cmp : cmps) { const int siz = cmp.size(); for (int i = 0; i < siz; ++i) idx[cmp[i]] = i; std::vector<std::vector<int>> h(siz); for (int u : cmp) for (int v : g[u]) { h[idx[u]].push_back(idx[v]); } std::vector<int> val = rec(rec, h); const int l = pd.size() - 1, r = val.size() - 1; std::vector<int> dp(l + r + 1); for (int i = 0; i <= l; ++i) { for (int j = 0; j <= r; ++j) { dp[i + j] = std::max(dp[i + j], pd[i] + val[j]); } } pd.swap(dp); } return pd; } }, &g]{ return rec(rec, g); }(); std::cout << *std::max_element(res.begin(), res.end()) << std::endl; }