Cover It!

Explicación

Para resolver este problema, hay que hallar un bicoloreo (bipartite coloring) donde cada nodo está seleccionado o es adyacente a uno que lo está.

Hacemos BFS desde cualquier nodo y calculamos la distancia (nivel) de la raíz a cada nodo. Cada nodo tendrá paridad par o impar.

Como BFS visita todos los nodos del mismo nivel antes de seguir, las aristas deben conectar nodos de paridades opuestas. Esto da la bipartición que separa a cada nodo.

Las categorías son disjuntas y exhaustivas, así que un grupo debe tener a lo sumo $\left \lfloor \frac{n}{2} \right \rfloor$ nodos. Podemos imprimir el menor de los dos conjuntos para cumplir los requisitos del problema.

Otra interpretación es que el recorrido BFS construye un árbol de expansión, sobre el que hacemos un bicoloreo. Como hacer un bicoloreo sobre el árbol cumple el requisito, podemos ignorar todas las aristas que no forman parte de nuestro árbol de expansión.

Implementación

Complejidad temporal: $\mathcal{O}(N+M)$

C++JavaPython


#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);
		for (int i = 0; i < m; i++) {
			int u, v;
			cin >> u >> v;
			adj[--u].push_back(--v);
			adj[v].push_back(u);
		}
 
		// BFS desde el nodo 0
		queue<int> q;
		q.push(0);
		vector<int> dist(n, -1);
		dist[0] = 0;
		while (!q.empty()) {
			int curr = q.front();
			q.pop();
			for (int next : adj[curr]) {
				if (dist[next] == -1) {
					dist[next] = dist[curr] + 1;
					q.push(next);
				}
			}
		}
 
		// separamos los nodos por paridad e imprimimos el grupo más chico
		vector<int> even;
		vector<int> odd;
 
		for (int i = 0; i < n; i++) {
			(dist[i] % 2 == 0 ? even : odd).push_back(i + 1);
		}
		if (even.size() < odd.size()) {
			cout << even.size() << "\n";
			for (int num : even) { cout << num << " "; }
		} else {
			cout << odd.size() << "\n";
			for (int num : odd) { cout << num << " "; }
		}
		cout << "\n";
	}
}


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++) {
			String[] nm = br.readLine().split(" ");
			int n = Integer.parseInt(nm[0]);
			int m = Integer.parseInt(nm[1]);
			List<Integer>[] adj = new ArrayList[n];
			for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
			for (int i = 0; i < m; i++) {
				String[] uv = br.readLine().split(" ");
				int u = Integer.parseInt(uv[0]) - 1;
				int v = Integer.parseInt(uv[1]) - 1;
				adj[u].add(v);
				adj[v].add(u);
			}
 
			// BFS desde el nodo 0
			Queue<Integer> q = new LinkedList<>();
			int[] dist = new int[n];
			Arrays.fill(dist, -1);
			q.add(0);
			dist[0] = 0;
			while (!q.isEmpty()) {
				int curr = q.poll();
				for (int next : adj[curr]) {
					if (dist[next] == -1) {
						dist[next] = dist[curr] + 1;
						q.add(next);
					}
				}
			}
 
			// separamos los nodos por paridad e imprimimos el grupo más chico
			List<Integer> even = new ArrayList<>();
			List<Integer> odd = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				if (dist[i] % 2 == 0) {
					even.add(i + 1);
				} else {
					odd.add(i + 1);
				}
			}
			List<Integer> smaller = even.size() <= odd.size() ? even : odd;
			pw.println(smaller.size());
			for (int num : smaller) { pw.print(num + " "); }
			pw.println();
		}
 
		pw.close();
		br.close();
	}
}


from collections import deque
import sys
 
input = sys.stdin.readline  # redefinimos input por rendimiento
 
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())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
 
	# BFS desde el nodo 0
	dist = [-1] * n
	dist[0] = 0
	q = deque([0])
	while q:
		curr = q.popleft()
		for next in adj[curr]:
			if dist[next] == -1:
				dist[next] = dist[curr] + 1
				q.append(next)
 
	# separamos los nodos por paridad e imprimimos el grupo más chico
	even = []
	odd = []
	for i in range(n):
		if dist[i] % 2 == 0:
			even.append(i + 1)
		else:
			odd.append(i + 1)
 
	smaller = even if len(even) <= len(odd) else odd
	print(len(smaller))
	print(" ".join(map(str, smaller)))