Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
A candy subgraph is just an edge subset where every vertex is used by at most two chosen edges. So forget the strawberry lore: this is a maximum cardinality -matching.
Do not assume the chosen subgraph has to stay connected. It can be any pile of paths and cycles. The only thing that matters locally is how many incident chosen edges each vertex gets.
Pretend every original vertex has two available slots. Choosing an original edge should consume one slot of and one slot of .
The annoying part is that a normal matching on duplicated vertices could choose the same original edge twice. Fix that with an edge gadget: two gadget vertices for each original edge, plus an internal fallback edge.
Build a general matching instance where every original edge contributes a baseline internal match worth , and taking that original edge instead gives two matches. Then the answer is maximum_matching_size - m. Yes, this is Blossom territory.
We need the maximum number of edges we can keep while every vertex has degree at most .
That is exactly a maximum cardinality 2-matching in a general graph: every vertex has capacity , every edge has capacity , maximize chosen edges.
The cycle condition in the statement is not something we need to wrestle with for this solution. It makes the original problem more structured, but the cleanest way through is to solve the stronger general problem. Local greedy path/cycle thinking is a trap; it looks tempting, then immediately starts lying to you.
The slot idea
For every original vertex , create two slot vertices:
If an original edge incident to is chosen, it must occupy one of these slots. Since there are only two slots, at most two chosen edges can touch .
So far, this sounds like matching. But there is a catch: if we simply duplicate vertices and connect copies, the same original edge might be chosen twice using different copies. That is illegal. Edge capacity is .
We need a gadget per edge.
The edge gadget
For each original edge , create two new vertices and .
Add these matching edges:
Now look at what a matching can do with this gadget.
If we do not choose original edge , we can match with . That gives matching edge.
If we do choose original edge , we instead match:
That gives matching edges.
So choosing an original edge improves the matching size by exactly compared to the baseline fallback. Since there are original edges, the baseline size is . Therefore:
No magic. Just a gadget doing accounting like a tiny bureaucrat.
Why this is correct
First direction: suppose we have a valid candy subgraph with chosen edges.
For every chosen original edge , match its gadget vertices to free slots of and . This is possible because each original vertex has degree at most in the chosen subgraph, so its two slots are enough.
For every unchosen original edge, use its internal fallback edge.
Then the matching size is:
So the maximum matching size is at least .
Second direction: suppose we have any matching in the gadget graph.
Call an original edge selected only if both gadget vertices are matched outward to endpoint slots. Those selected edges form a valid candy subgraph, because every original vertex has only two slots total.
For an unselected gadget, the matching can contribute at most edge: either the internal fallback, one outward slot edge, or nothing. For a selected gadget, it contributes exactly .
If gadgets are selected, total matching size is at most:
So , and is a valid candy answer. That means no matching can overstate the real optimum.
Together, the optimum candy size is exactly max_matching - m.
Computing the matching
The gadget graph is not necessarily bipartite, so ordinary Kuhn or max-flow matching is not enough. We need maximum matching in a general graph, i.e. Edmonds' Blossom algorithm.
The implementation below uses the standard unweighted Blossom algorithm with blossom contraction and BFS alternating trees.
The gadget has:
So the graph is small enough here. The final answer for each test case is just:
blossom_max_matching(gadget) - m#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Blossom {
int n, timer = 0;
vector<vector<int>> g;
vector<int> match, parent, base, q, used, in_blossom, seen;
Blossom(int n) : n(n), g(n), match(n, -1), parent(n), base(n), q(n), used(n), in_blossom(n), seen(n, 0) {}
void addEdge(int u, int v) {
if (u == v) return;
g[u].push_back(v);
g[v].push_back(u);
}
int lca(int a, int b) {
++timer;
while (true) {
a = base[a];
seen[a] = timer;
if (match[a] == -1) break;
a = parent[match[a]];
}
while (true) {
b = base[b];
if (seen[b] == timer) return b;
b = parent[match[b]];
}
}
void markPath(int v, int b, int child) {
while (base[v] != b) {
in_blossom[base[v]] = in_blossom[base[match[v]]] = 1;
parent[v] = child;
child = match[v];
v = parent[match[v]];
}
}
int findPath(int root) {
fill(used.begin(), used.end(), 0);
fill(parent.begin(), parent.end(), -1);
iota(base.begin(), base.end(), 0);
int head = 0, tail = 0;
q[tail++] = root;
used[root] = 1;
while (head < tail) {
int v = q[head++];
for (int u : g[v]) {
if (base[v] == base[u] || match[v] == u) continue;
if (u == root || (match[u] != -1 && parent[match[u]] != -1)) {
int cur = lca(v, u);
fill(in_blossom.begin(), in_blossom.end(), 0);
markPath(v, cur, u);
markPath(u, cur, v);
for (int i = 0; i < n; i++) {
if (in_blossom[base[i]]) {
base[i] = cur;
if (!used[i]) {
used[i] = 1;
q[tail++] = i;
}
}
}
} else if (parent[u] == -1) {
parent[u] = v;
if (match[u] == -1) return u;
int w = match[u];
used[w] = 1;
q[tail++] = w;
}
}
}
return -1;
}
int maxMatching() {
int res = 0;
for (int i = 0; i < n; i++) {
if (match[i] != -1) continue;
int v = findPath(i);
if (v == -1) continue;
while (v != -1) {
int pv = parent[v];
int nv = match[pv];
match[v] = pv;
match[pv] = v;
v = nv;
}
res++;
}
return res;
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<pair<int, int>> edges(m);
for (auto &[u, v] : edges) {
cin >> u >> v;
--u;
--v;
}
int total = 2 * n + 2 * m;
Blossom bm(total);
auto slot = [](int v, int id) {
return 2 * v + id;
};
int start = 2 * n;
for (int i = 0; i < m; i++) {
auto [u, v] = edges[i];
int a = start + 2 * i;
int b = a + 1;
bm.addEdge(a, b);
bm.addEdge(a, slot(u, 0));
bm.addEdge(a, slot(u, 1));
bm.addEdge(b, slot(v, 0));
bm.addEdge(b, slot(v, 1));
}
cout << bm.maxMatching() - m << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Blossom {
int n, timer = 0;
vector<vector<int>> g;
vector<int> match, parent, base, q, used, in_blossom, seen;
Blossom(int n) : n(n), g(n), match(n, -1), parent(n), base(n), q(n), used(n), in_blossom(n), seen(n, 0) {}
void addEdge(int u, int v) {
if (u == v) return;
g[u].push_back(v);
g[v].push_back(u);
}
int lca(int a, int b) {
++timer;
while (true) {
a = base[a];
seen[a] = timer;
if (match[a] == -1) break;
a = parent[match[a]];
}
while (true) {
b = base[b];
if (seen[b] == timer) return b;
b = parent[match[b]];
}
}
void markPath(int v, int b, int child) {
while (base[v] != b) {
in_blossom[base[v]] = in_blossom[base[match[v]]] = 1;
parent[v] = child;
child = match[v];
v = parent[match[v]];
}
}
int findPath(int root) {
fill(used.begin(), used.end(), 0);
fill(parent.begin(), parent.end(), -1);
iota(base.begin(), base.end(), 0);
int head = 0, tail = 0;
q[tail++] = root;
used[root] = 1;
while (head < tail) {
int v = q[head++];
for (int u : g[v]) {
if (base[v] == base[u] || match[v] == u) continue;
if (u == root || (match[u] != -1 && parent[match[u]] != -1)) {
int cur = lca(v, u);
fill(in_blossom.begin(), in_blossom.end(), 0);
markPath(v, cur, u);
markPath(u, cur, v);
for (int i = 0; i < n; i++) {
if (in_blossom[base[i]]) {
base[i] = cur;
if (!used[i]) {
used[i] = 1;
q[tail++] = i;
}
}
}
} else if (parent[u] == -1) {
parent[u] = v;
if (match[u] == -1) return u;
int w = match[u];
used[w] = 1;
q[tail++] = w;
}
}
}
return -1;
}
int maxMatching() {
int res = 0;
for (int i = 0; i < n; i++) {
if (match[i] != -1) continue;
int v = findPath(i);
if (v == -1) continue;
while (v != -1) {
int pv = parent[v];
int nv = match[pv];
match[v] = pv;
match[pv] = v;
v = nv;
}
res++;
}
return res;
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<pair<int, int>> edges(m);
for (auto &[u, v] : edges) {
cin >> u >> v;
--u;
--v;
}
int total = 2 * n + 2 * m;
Blossom bm(total);
auto slot = [](int v, int id) {
return 2 * v + id;
};
int start = 2 * n;
for (int i = 0; i < m; i++) {
auto [u, v] = edges[i];
int a = start + 2 * i;
int b = a + 1;
bm.addEdge(a, b);
bm.addEdge(a, slot(u, 0));
bm.addEdge(a, slot(u, 1));
bm.addEdge(b, slot(v, 0));
bm.addEdge(b, slot(v, 1));
}
cout << bm.maxMatching() - m << '\n';
}
}