Official Analysis (C++)

Explanation

To solve this problem, we need to find a bipartite coloring where every node is either selected or adjacent to one that is.

Perform BFS starting from any node and calculate the distance (level) from the root to each node. Every node will have a parity of even or odd.

Since BFS visits every node at the same level before moving on, edges must connect nodes of opposite parities. This provides the bipartition that separates every node.

The categories are disjoint and exhaustive, so one group must have less than or equal to $\left \lfloor \frac{n}{2} \right \rfloor$ nodes. We can output the smaller of the two sets to satisfy the problem's requirements.

Another interpretation is that the BFS traversal constructs a spanning tree, which we do a bipartite coloring on. Because doing a bipartite coloring on the tree satisfies the requirement, we can ignore all edges that aren't part of our spanning tree.

Implementation

Time Complexity: $\mathcal{O}(N+M)$

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

int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, m;
		cin >> n >> m;
		vector<vector<int>> adj(n);

Copy
import java.io.*;
import java.util.*;

public class Cover {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

		int testNum = Integer.parseInt(br.readLine());
		for (int t = 0; t < testNum; t++) {

Copy
from collections import deque
import sys

input = sys.stdin.readline  # redefine input for performance reasons

for _ in range(int(input())):
	n, m = map(int, input().split())
	adj = [[] for _ in range(n)]
	for _ in range(m):
		u, v = map(int, input().split())