Strange Housing (Codeforces 1471F)
Tags: Greedy, dfs and similar

Students of Winter Informatics School are going to live in a set of houses connected by underground passages. Teachers are also going to live in some of these houses, but they can not be accommodated randomly. For safety reasons, the following must hold:  All passages between two houses will be closed, if there are no teachers in both of them. All other passages will stay open.  It should be possible to travel between any two houses using the underground passages that are open.  Teachers should not live in houses, directly connected by a passage. Please help the organizers to choose the houses where teachers will live to satisfy the safety requirements or determine that it is impossible.

Input: The first input line contains a single integer $$$t$$$ — the number of test cases ($$$1 \le t \le 10^5$$$). Each test case starts with two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$0 \le m \le 3 \cdot 10^5$$$) — the number of houses and the number of passages.Then $$$m$$$ lines follow, each of them contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), describing a passage between the houses $$$u$$$ and $$$v$$$. It is guaranteed that there are no two passages connecting the same pair of houses.The sum of values $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$, and the sum of values $$$m$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, if there is no way to choose the desired set of houses, output "NO". Otherwise, output "YES", then the total number of houses chosen, and then the indices of the chosen houses in arbitrary order.

Note: The picture below shows the second example test.   

Sample Inputs:
2
3 2
3 2
2 1
4 2
1 4
2 3

1
17 27
1 8
2 9
3 10
4 11
5 12
6 13
7 14
8 9
8 14
8 15
9 10
9 15
10 11
10 15
10 17
11 12
11 17
12 13
12 16
12 17
13 14
13 16
14 16
14 15
15 16
15 17
16 17

Sample Outputs:
YES
2
1 3 
NO

YES
8
1 3 4 5 6 9 14 17

Solution (Python):
""""""
import os
import sys
from io import BytesIO, IOBase
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')

def RL():
    return map(int, sys.stdin.readline().rstrip().split())

def RLL():
    return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
    return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
    if mod:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr) % mod)
    else:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr))
    return farr[x]

def ifact(x, mod):
    global ifa
    fact(x, mod)
    ifa.append(pow(farr[-1], mod - 2, mod))
    for i in range(x, 0, -1):
        ifa.append(ifa[-1] * i % mod)
    ifa.reverse()

def per(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return fact(i) // fact(i - j)
    return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return per(i, j) // fact(j)
    return per(i, j, mod) * ifa[j] % mod

def catalan(n):
    return com(2 * n, n) // (n + 1)

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def floorsum(a, b, c, n):
    if a == 0:
        return b // c * (n + 1)
    if a >= c or b >= c:
        return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
    m = (a * n + b) // c
    return n * m - floorsum(c, c - b - 1, a, m - 1)

def lowbit(n):
    return n & -n

def inverse(a, m):
    a %= m
    if a <= 1:
        return a
    return (1 - inverse(m, a) * m) // a % m

class BIT:

    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr) - 1

    def update(self, x, v):
        while x <= self.n:
            self.arr[x] += v
            x += x & -x

    def query(self, x):
        ans = 0
        while x:
            ans += self.arr[x]
            x &= x - 1
        return ans
''

class DSU:

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

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

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

    def union(self, u, v):
        (u, v) = (self.find(u), self.find(v))
        if u == v:
            return False
        if self.c[u] > self.c[v]:
            (u, v) = (v, u)
        self.c[u] += self.c[v]
        self.c[v] = u
        return True

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

class UFS:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv

def Prime(n):
    c = 0
    prime = []
    flag = [0] * (n + 1)
    for i in range(2, n + 1):
        if not flag[i]:
            prime.append(i)
            c += 1
        for j in range(c):
            if i * prime[j] > n:
                break
            flag[i * prime[j]] = prime[j]
            if i % prime[j] == 0:
                break
    return flag

def dij(s, graph):
    d = {}
    d[s] = 0
    heap = [(0, s)]
    seen = set()
    while heap:
        (dis, u) = heappop(heap)
        if u in seen:
            continue
        seen.add(u)
        for (v, w) in graph[u]:
            if v not in d or d[v] > d[u] + w:
                d[v] = d[u] + w
                heappush(heap, (d[v], v))
    return d

def GP(it):
    return [[ch, len(list(g))] for (ch, g) in groupby(it)]

def lcm(a, b):
    return a * b // gcd(a, b)

def lis(nums):
    res = []
    for k in nums:
        i = bisect.bisect_left(res, k)
        if i == len(res):
            res.append(k)
        else:
            res[i] = k
    return len(res)

class DLN:

    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None

def nb(i, j):
    for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < n and 0 <= nj < m:
            yield (ni, nj)

def topo(n):
    q = deque()
    res = []
    for i in range(1, n + 1):
        if ind[i] == 0:
            q.append(i)
            res.append(i)
    while q:
        u = q.popleft()
        for v in g[u]:
            ind[v] -= 1
            if ind[v] == 0:
                q.append(v)
                res.append(v)
    return res

@bootstrap
def gdfs(r, p):
    if len(g[r]) == 1 and p != -1:
        yield None
    for ch in g[r]:
        if ch != p:
            yield gdfs(ch, r)
    yield None
t = N()
for i in range(t):
    (n, m) = RL()
    g = [[] for i in range(n + 1)]
    for i in range(m):
        (u, v) = RL()
        g[u].append(v)
        g[v].append(u)
    color = [-1] * (n + 1)
    res = [1]
    p = set()
    color[1] = 1
    nb = []
    for v in g[1]:
        color[v] = 0
        nb.append(v)
    for u in nb:
        for v in g[u]:
            if color[v] == -1:
                p.add(v)
    while p:
        i = p.pop()
        color[i] = 1
        res.append(i)
        nb = []
        for v in g[i]:
            if color[v] == -1:
                color[v] = 0
                p.discard(v)
                nb.append(v)
        for u in nb:
            for v in g[u]:
                if color[v] == -1:
                    p.add(v)
    if any((color[i] == -1 for i in range(1, n + 1))):
        print('NO')
    else:
        print('YES')
        print(len(res))
        print(*res)
''
''

Solution (Python):
import os, io, heapq
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    graph = [[] for i in range(n)]
    visited = [0] * n
    visited2 = [0] * n
    ans = []
    stack = [0]
    for i in range(m):
        (u, v) = map(int, input().split())
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)
    while stack:
        curr = stack.pop()
        if visited2[curr]:
            continue
        visited[curr] = 1
        ans.append(curr + 1)
        for x in graph[curr]:
            if visited2[x]:
                continue
            visited2[x] = 1
            for y in graph[x]:
                if visited[y] or visited2[y]:
                    continue
                stack.append(y)
                visited[y] = 1
    flag = 0
    for i in range(n):
        if not (visited[i] or visited2[i]):
            flag = 1
    if flag == 0:
        print('YES')
        print(str(len(ans)))
        print(' '.join(map(str, ans)))
    else:
        print('NO')

Solution (Python):
import os, sys
from io import BytesIO, IOBase
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))
try:
    (sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
    pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import *
from math import *

def fun(s, color):
    vis = [False] * n
    vis[s] = True
    color = [-1] * n
    color[s] = 1
    queue = deque([])
    queue.append(s)
    while queue:
        v = queue.popleft()
        for u in graph[v]:
            if not vis[u]:
                vis[u] = 1
                color[u] = 1 - color[v]
                queue.append(u)
            elif color[u] == color[v] == 1:
                color[u] = 0
                queue.append(u)
    return color
for _ in range(ii1()):
    (n, m) = iia()
    graph = [[] for i in range(n)]
    for _ in range(m):
        (u, v) = iia()
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)
    col = fun(0, 1)
    if -1 in col:
        print('NO')
    else:
        print('YES')
        ans = []
        for (idx, c) in enumerate(col):
            if c == 1:
                ans.append(idx + 1)
        print(len(ans))
        print(*ans)