C++ Library for Competitive Programming
/*
* @title グラフ/二部グラフ判定
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/arc099/tasks/arc099_c
*/
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include "emthrm/data_structure/union-find/union-find.hpp"
#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/is_bipartite.hpp"
int main() {
int n, m;
std::cin >> n >> m;
int ans = m;
std::vector<std::vector<bool>> is_adjacent(n, std::vector<bool>(n, false));
while (m--) {
int a, b;
std::cin >> a >> b;
--a; --b;
is_adjacent[a][b] = true;
is_adjacent[b][a] = true;
}
emthrm::UnionFind union_find(n);
std::vector<std::vector<emthrm::Edge<bool>>> graph(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (!is_adjacent[i][j]) {
union_find.unite(i, j);
graph[i].emplace_back(i, j);
graph[j].emplace_back(j, i);
}
}
}
const std::vector<int> color = emthrm::is_bipartite(graph);
if (color.empty()) {
std::cout << "-1\n";
return 0;
}
std::vector<bool> dp(n + 1, false);
dp[0] = true;
std::map<int, int> mp;
for (int i = 0; i < n; ++i) {
mp[union_find.root(i)] += color[i];
}
for (const auto& [root, size] : mp) {
for (int i = n; i >= 0; --i) {
if (dp[i]) {
dp[i] = false;
if (i + size <= n) dp[i + size] = true;
if (i + union_find.size(root) - size <= n) {
dp[i + union_find.size(root) - size] = true;
}
}
}
}
for (int i = 0; i <= n; ++i) {
if (dp[i]) ans = std::min(ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
}
std::cout << ans << '\n';
return 0;
}
#line 1 "test/graph/is_bipartite.test.cpp"
/*
* @title グラフ/二部グラフ判定
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/arc099/tasks/arc099_c
*/
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#line 1 "include/emthrm/data_structure/union-find/union-find.hpp"
#include <utility>
#line 6 "include/emthrm/data_structure/union-find/union-find.hpp"
namespace emthrm {
struct UnionFind {
explicit UnionFind(const int n) : data(n, -1) {}
int root(const int ver) {
return data[ver] < 0 ? ver : data[ver] = root(data[ver]);
}
bool unite(int u, int v) {
u = root(u);
v = root(v);
if (u == v) return false;
if (data[u] > data[v]) std::swap(u, v);
data[u] += data[v];
data[v] = u;
return true;
}
bool is_same(const int u, const int v) { return root(u) == root(v); }
int size(const int ver) { return -data[root(ver)]; }
private:
std::vector<int> data;
};
} // namespace emthrm
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/is_bipartite.hpp"
#include <ranges>
#line 6 "include/emthrm/graph/is_bipartite.hpp"
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 8 "include/emthrm/graph/is_bipartite.hpp"
namespace emthrm {
template <typename CostType>
std::vector<int> is_bipartite(
const std::vector<std::vector<Edge<CostType>>>& graph) {
const int n = graph.size();
std::vector<int> color(n, -1);
const auto dfs = [&graph, &color](auto dfs, const int ver, const int c)
-> bool {
color[ver] = c;
for (const int e : graph[ver]
| std::views::transform(&Edge<CostType>::dst)) {
if (color[e] == c || (color[e] == -1 && !dfs(dfs, e, c ^ 1))) {
return false;
}
}
return true;
};
for (int i = 0; i < n; ++i) {
if (color[i] == -1 && !dfs(dfs, i, 0)) return std::vector<int>{};
}
return color;
}
} // namespace emthrm
#line 16 "test/graph/is_bipartite.test.cpp"
int main() {
int n, m;
std::cin >> n >> m;
int ans = m;
std::vector<std::vector<bool>> is_adjacent(n, std::vector<bool>(n, false));
while (m--) {
int a, b;
std::cin >> a >> b;
--a; --b;
is_adjacent[a][b] = true;
is_adjacent[b][a] = true;
}
emthrm::UnionFind union_find(n);
std::vector<std::vector<emthrm::Edge<bool>>> graph(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (!is_adjacent[i][j]) {
union_find.unite(i, j);
graph[i].emplace_back(i, j);
graph[j].emplace_back(j, i);
}
}
}
const std::vector<int> color = emthrm::is_bipartite(graph);
if (color.empty()) {
std::cout << "-1\n";
return 0;
}
std::vector<bool> dp(n + 1, false);
dp[0] = true;
std::map<int, int> mp;
for (int i = 0; i < n; ++i) {
mp[union_find.root(i)] += color[i];
}
for (const auto& [root, size] : mp) {
for (int i = n; i >= 0; --i) {
if (dp[i]) {
dp[i] = false;
if (i + size <= n) dp[i + size] = true;
if (i + union_find.size(root) - size <= n) {
dp[i + union_find.size(root) - size] = true;
}
}
}
}
for (int i = 0; i <= n; ++i) {
if (dp[i]) ans = std::min(ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
}
std::cout << ans << '\n';
return 0;
}