The problem involves finding the minimum number of vertices to remove from an undirected graph to make it disconnected.

Problem Analysis When a graph becomes disconnected, there exist at least two vertices that cannot reach each other. We can enumerate these two vertices as source and sink, then determine the minimum number of other vertices that need to be removed to separate them.

This naturally leads to the concept of minimum cut. However, the standard minimum cut applies to edges, while our task requires removing vertices. To bridge this gap, we employ a vertex splitting technique.

Vertex Splitting Transformation The core idea is to convert vertex deletion into edge deletion. For each original vertex u, we create two nodes: u and u', where u' = u + n. The transformation works as follows:

For every vertex u, add a directed edge from u to u' with capacity 1 (except for source and sink vertices) For each undirected edge (u, v) in the original graph, add directed edges u' → v and v' → u with infinite capacity

After this transformation, deleting vertex u is equivalent to cutting the edge u → u', which has capacity 1. The original graph edges remain intact since they carry infinite capacity and cannot contribute to the minimum cut.

Algorithm For each pair of distinct vertices s and t, treat s' = s + n as the source and t as the sink. Compute the minimum s-t cut using max-flow. The answer is the minimum value across all vertex pairs.

By the max-flow min-cut theorem, the maximum flow value equals the minimum cut value.

Correctness Proof Consider the structure after vertex splitting: original incoming edges to u now point to u, while original outgoing edges from u now originate from u'. If we cut the edge u → u', vertices reachable from original incoming edges to u cannot reach vertices that originally were reachable from u. This effectively simulates the removal of vertex u.

Since original graph edges have infinite capacity, they will never be part of any finite cut, ensuring that only vertex-spltiting edges can be cut.

Implementation Details The input uses 0-based vertex indexing. We use Dinic's algorithm for maximum flow computation. Important implementation notes:

Convert all vertices to 1-based indexing Initialize edge residual capacities before each max-flow computation Handle the special case where the graph has no edges

Reference Implementation

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INFINITY = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int n, m;
        cin >> n >> m;
        
        // Store edges for reconstruction
        vector<pair<int,int>> edges;
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            edges.emplace_back(++u, ++v);  // convert to 1-based
        }
        
        if (m == 0) {
            cout << 0 << "\n";
            continue;
        }
        
        const int TOTAL_NODES = 2 * n + 2;
        const int SRC_OFFSET = n;
        
        auto build_network = [&](int source, int sink) -> ll {
            struct Edge { int to; ll cap; int rev; };
            vector<vector<Edge>> graph(TOTAL_NODES);
            
            auto add_edge = [&](int from, int to, ll cap) {
                Edge a{to, cap, (int)graph[to].size()};
                Edge b{from, 0, (int)graph[from].size()};
                graph[from].push_back(a);
                graph[to].push_back(b);
            };
            
            // Vertex splitting for each node
            for (int i = 1; i <= n; ++i) {
                if (i != source && i != sink) {
                    add_edge(i, i + SRC_OFFSET, 1);
                }
            }
            
            // Original edges
            for (auto& [u, v] : edges) {
                int u_split = u + SRC_OFFSET;
                int v_split = v + SRC_OFFSET;
                add_edge(u_split, v, INFINITY);
                add_edge(v_split, u, INFINITY);
            }
            
            int real_source = source + SRC_OFFSET;
            int real_sink = sink;
            
            // Dinic's algorithm
            vector<int> level(TOTAL_NODES);
            vector<int> ptr(TOTAL_NODES);
            
            auto bfs = [&]() -> bool {
                fill(level.begin(), level.end(), -1);
                queue<int> q;
                q.push(real_source);
                level[real_source] = 0;
                
                while (!q.empty()) {
                    int u = q.front();
                    q.pop();
                    for (const auto& e : graph[u]) {
                        if (e.cap > 0 && level[e.to] == -1) {
                            level[e.to] = level[u] + 1;
                            q.push(e.to);
                        }
                    }
                }
                return level[real_sink] != -1;
            };
            
            function<ll(int,ll)> dfs = [&](int u, ll pushed) -> ll {
                if (u == real_sink || pushed == 0) return pushed;
                for (int& cid = ptr[u]; cid < (int)graph[u].size(); ++cid) {
                    Edge& e = graph[u][cid];
                    if (e.cap > 0 && level[e.to] == level[u] + 1) {
                        ll tr = dfs(e.to, min(pushed, e.cap));
                        if (tr == 0) continue;
                        e.cap -= tr;
                        graph[e.to][e.rev].cap += tr;
                        return tr;
                    }
                }
                return 0;
            };
            
            ll flow = 0;
            while (bfs()) {
                fill(ptr.begin(), ptr.end(), 0);
                while (ll pushed = dfs(real_source, INFINITY)) {
                    flow += pushed;
                }
            }
            return flow;
        };
        
        int answer = n;
        for (int s = 1; s <= n; ++s) {
            for (int t = 1; t < s; ++t) {
                int result = build_network(s, t);
                answer = min(answer, result);
            }
        }
        cout << answer << "\n";
    }
    return 0;
}

Bug Corrections The original implementation contained three bugs that have been fixed:

Added edges in both directions for vertex splitting, which is incorrect. Only forward edges (capacity 1) are needed. Failed to convert 0-based input indices to 1-based storage. Special-cased zero-edge graphs incorrectly. The empty graph case is naturally handled by the enumeration.