Make It Connected (Codeforces 1761E)
Tags: Greedy, matrices

You are given a simple undirected graph consisting of $$$n$$$ vertices. The graph doesn't contain self-loops, there is at most one edge between each pair of vertices. Your task is simple: make the graph connected.You can do the following operation any number of times (possibly zero):  Choose a vertex $$$u$$$ arbitrarily.  For each vertex $$$v$$$ satisfying $$$v\ne u$$$ in the graph individually, if $$$v$$$ is adjacent to $$$u$$$, remove the edge between $$$u$$$ and $$$v$$$, otherwise add an edge between $$$u$$$ and $$$v$$$. Find the minimum number of operations required to make the graph connected. Also, find any sequence of operations with the minimum length that makes the graph connected.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 800$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 4000$$$) — the number of vertices in the graph.Then $$$n$$$ lines follow. The $$$i$$$-th row contains a binary string $$$s_i$$$ of length $$$n$$$, where $$$s_{i,j}$$$ is '1' if there is an edge between vertex $$$i$$$ and $$$j$$$ initially, otherwise $$$s_{i,j}$$$ is '0'.It is guaranteed that $$$s_{i,i}$$$ is always '0' and $$$s_{i,j}=s_{j,i}$$$ for $$$1\leq i,j\leq n$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4000$$$.

Output: For each test case, in the first line, output an integer $$$m$$$  — the minimum number of operations required.If $$$m$$$ is greater than zero, then print an extra line consisting of $$$m$$$ integers — the vertices chosen in the operations in your solution. If there are multiple solutions with the minimum number of operations, print any.

Note: In the first test case, the graph is connected at the beginning, so the answer is $$$0$$$.In the second test case, if we do the operation with vertex $$$1$$$, we will get the following graph represented by an adjacency matrix:$$$$$$ \begin{bmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{bmatrix} $$$$$$It's obvious that the graph above is connected.In the third test case, if we do the operation with vertex $$$3$$$ and $$$4$$$, we will get the following graph represented by an adjacency matrix:$$$$$$ \begin{bmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{bmatrix} $$$$$$It's obvious that the graph above is connected, and it can be proven that we can't perform less than $$$2$$$ operations to make the graph connected.

Sample Inputs:
4
3
011
100
100
3
000
001
010
4
0100
1000
0001
0010
6
001100
000011
100100
101000
010001
010010

Sample Outputs:
0
1
1
2
3 4 
3
2 5 6

Solution (Python):
from collections import deque
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for i in range(t):
    n = int(input())
    q = {}
    c = {}
    for j in range(1, n + 1):
        q[j] = []
        y = input().decode('utf-8')
        for k in range(1, n + 1):
            if y[k - 1] == '1':
                q[j].append(k)
        c[j] = len(q[j])
    res = []
    check = set()
    for j in range(1, n + 1):
        if j not in check:
            res.append([j])
            check.add(j)
            new = deque([j])
            while new:
                x = new.pop()
                for k in q[x]:
                    if k not in check:
                        check.add(k)
                        new.appendleft(k)
                        res[-1].append(k)
    rho = len(res)
    if rho == 1:
        print(0)
    elif rho == 2:
        for j in res:
            zeta = len(j)
            if zeta == 1:
                print(1)
                print(j[0])
                break
            mniota = zeta - 1
            mny = 0
            for k in j:
                if c[k] < mniota:
                    mniota = c[k]
                    mny = k
            if mniota < zeta - 1:
                print(1)
                print(mny)
                break
        else:
            mn = n
            delta = 0
            for j in range(rho):
                if mn >= len(res[j]):
                    mn = min(mn, len(res[j]))
                    delta = j
            print(mn)
            print(' '.join([str(k) for k in res[delta]]))
    else:
        for j in res:
            zeta = len(j)
            if zeta == 1:
                print(1)
                print(j[0])
                break
            mniota = zeta - 1
            mny = 0
            for k in j:
                if c[k] < mniota:
                    mniota = c[k]
                    mny = k
            if mniota < zeta - 1:
                print(1)
                print(mny)
                break
        else:
            print(2)
            print(res[0][0], res[1][0])

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from functools import lru_cache
from itertools import accumulate
import math
import sys
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ii = lambda : int(input())
mii = lambda : map(int, input().split())
fii = lambda : map(float, input().split())
lmii = lambda : list(map(int, input().split()))
i2c = lambda n: chr(ord('a') + n)
c2i = lambda c: ord(c) - ord('a')
mod = 998244353

def solve():
    n = ii()
    graph = []
    for i in range(n):
        graph.append(input())
    parents = list(range(n))

    def find(x):
        if x == parents[x]:
            return x
        else:
            parents[x] = find(parents[x])
            return parents[x]

    def merge(x, y):
        (x_, y_) = (find(x), find(y))
        parents[y_] = x_
    for i in range(n):
        for j in range(n):
            if graph[i][j] == '1':
                merge(i, j)
    d = {}
    for i in range(n):
        i_ = find(i)
        if i_ not in d:
            d[i_] = []
        d[i_].append(i)

    def is_complete(il):
        if len(il) < 2:
            return False
        else:
            for i in il:
                for j in il:
                    if i != j and graph[i][j] == '0':
                        return False
        return True

    def no_tarjan(il):
        if len(il) == 1:
            return il[0]
        min_de = len(il)
        min_i = -1
        for i in il:
            de = 0
            for j in il:
                if graph[i][j] == '1':
                    de += 1
            if de < min_de:
                min_de = de
                min_i = i
        return min_i
    if len(d) == 1:
        print(0)
        return
    elif len(d) == 2:
        (i1, i2) = d.keys()
        if is_complete(d[i1]):
            if is_complete(d[i2]):
                if len(d[i1]) < len(d[i2]):
                    print(len(d[i1]))
                    for i in range(len(d[i1])):
                        d[i1][i] += 1
                    print(*d[i1])
                else:
                    print(len(d[i2]))
                    for i in range(len(d[i2])):
                        d[i2][i] += 1
                    print(*d[i2])
            else:
                print(1)
                print(no_tarjan(d[i2]) + 1)
        else:
            print(1)
            print(no_tarjan(d[i1]) + 1)
    else:
        for i_ in d:
            if not is_complete(d[i_]):
                print(1)
                print(no_tarjan(d[i_]) + 1)
                break
        else:
            print(2)
            dl = list(d.keys())
            print(d[dl[0]][0] + 1, d[dl[1]][0] + 1)
for _ in range(ii()):
    solve()

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
from collections import defaultdict

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

def check(n, mat, change, change2):
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):
            if (mat[i][j] == '1') ^ (change == i or change == j) ^ (change2 == i or change2 == j):
                uf.union(i, j)
    grp = uf.all_group_members()
    if len(grp) != 1:
        raise Exception

def solve():
    n = int(input())
    mat = []
    uf = UnionFind(n)
    cnt = [0] * n
    for i in range(n):
        s = input()
        mat.append(s)
        for j in range(i + 1, n):
            if s[j] == '1':
                uf.union(i, j)
                cnt[i] += 1
                cnt[j] += 1
    grp = uf.all_group_members()
    if len(grp) == 1:
        print(0)
        return
    cmp = []
    for g_id in grp:
        g = grp[g_id]
        s = len(g)
        mn = s
        res = -1
        for v in g:
            if cnt[v] != s - 1:
                if cnt[v] < mn:
                    mn = cnt[v]
                    res = v
        if res != -1:
            print(1)
            print(res + 1)
            return
        cmp.append((s, g))
    cmp.sort()
    ans = cmp[0][1]
    if cmp[0][0] == 1:
        print(len(ans))
        print(*[i + 1 for i in ans])
        return
    if len(cmp) >= 3:
        print(2)
        ans = [cmp[0][1][0]] + [cmp[1][1][0]]
        x = ans[0]
        y = ans[1]
        print(*[i + 1 for i in ans][:2])
        return
    else:
        print(len(ans))
        print(*[i + 1 for i in ans])
for _ in range(int(input())):
    solve()