Lenient Vertex Cover (Codeforces 1680F)
Tags: Others, divide and conquer

You are given a simple connected undirected graph, consisting of $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$.A vertex cover of a graph is a set of vertices such that each edge has at least one of its endpoints in the set.Let's call a lenient vertex cover such a vertex cover that at most one edge in it has both endpoints in the set.Find a lenient vertex cover of a graph or report that there is none. If there are multiple answers, then print any of them.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^6$$$; $$$n - 1 \le m \le \min(10^6, \frac{n \cdot (n - 1)}{2})$$$) — the number of vertices and the number of edges of the graph.Each of the next $$$m$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) — the descriptions of the edges.For each testcase, the graph is connected and doesn't have multiple edges. The sum of $$$n$$$ over all testcases doesn't exceed $$$10^6$$$. The sum of $$$m$$$ over all testcases doesn't exceed $$$10^6$$$.

Output: For each testcase, the first line should contain YES if a lenient vertex cover exists, and NO otherwise. If it exists, the second line should contain a binary string $$$s$$$ of length $$$n$$$, where $$$s_i = 1$$$ means that vertex $$$i$$$ is in the vertex cover, and $$$s_i = 0$$$ means that vertex $$$i$$$ isn't.If there are multiple answers, then print any of them.

Note: Here are the graphs from the first example. The vertices in the lenient vertex covers are marked red.   

Sample Inputs:
4
6 5
1 3
2 4
3 4
3 5
4 6
4 6
1 2
2 3
3 4
1 4
1 3
2 4
8 11
1 3
2 4
3 5
4 6
5 7
6 8
1 2
3 4
5 6
7 8
7 2
4 5
1 2
2 3
3 4
1 3
2 4

1
10 15
9 4
3 4
6 4
1 2
8 2
8 3
7 2
9 5
7 8
5 10
1 4
2 10
5 3
5 7
2 9

1
10 19
7 9
5 3
3 4
1 6
9 4
1 4
10 5
7 1
9 2
8 3
7 3
10 9
2 10
9 8
3 2
1 5
10 7
9 5
1 2

Sample Outputs:
YES
001100
NO
YES
01100110
YES
0110

YES
0101100100

YES
1010000011

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]

def make_graph(n, m, x):
    s = [0] * (n + 3)
    for i in range(m):
        (u, v) = (x[2 * i], x[2 * i + 1])
        s[u + 2] += 1
        s[v + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def bfs(s):
    q = []
    dist = [inf] * (n + 1)
    for i in s:
        q.append(i)
        dist[i] = 0
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        di = dist[i]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
                parent[j] = i
    return (q, dist, parent)

def dfs(s):
    st = [s]
    now = list(s0)
    visit = [0] * (n + 1)
    visit[s] = 1
    u = [s]
    while st:
        i = st[-1]
        if u[-1] ^ i:
            u.append(i)
        if now[i] == s0[i + 1]:
            st.pop()
            continue
        j = G[now[i]]
        if not visit[j]:
            visit[j] = 1
            st.append(j)
        now[i] += 1
    return u

def get_min(s, t):
    s += l1
    t += l1
    ans = inf
    while s <= t:
        if s % 2:
            ans = min(ans, tree[s])
            s += 1
        s >>= 1
        if not t % 2:
            ans = min(ans, tree[t])
            t -= 1
        t >>= 1
    return ans
t = int(input())
ans = []
inf = pow(10, 15) + 1
for _ in range(t):
    (n, m) = map(int, input().split())
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    size = [1 for _ in range(n + 1)]
    (x, y) = ([], [])
    for _ in range(m):
        (u, v) = map(int, input().split())
        if not same(u, v):
            unite(u, v)
            x.append(u)
            x.append(v)
        else:
            y.append(u)
            y.append(v)
    (G, s0) = make_graph(n, n - 1, x)
    (p, dist, parent) = bfs([1])
    t0 = dfs(1)
    t1 = [-1] * (n + 1)
    t2 = [-1] * (n + 1)
    l = len(t0)
    for i in range(l):
        if t1[t0[i]] == -1:
            t1[t0[i]] = i
    for i in range(l - 1, -1, -1):
        if t2[t0[i]] == -1:
            t2[t0[i]] = i
    l1 = pow(2, l.bit_length())
    l2 = 2 * l1
    tree = [inf] * l2
    for i in range(l):
        j = t0[i]
        (tree[i + l1], t2[j]) = (dist[j] * (n + 1) + j, i)
    for i in range(l1 - 1, 0, -1):
        tree[i] = min(tree[2 * i], tree[2 * i + 1])
    dp = [0] * (n + 1)
    z = []
    for i in range(0, len(y), 2):
        (u, v) = (y[i], y[i + 1])
        if t1[u] > t1[v]:
            (u, v) = (v, u)
        w = get_min(t1[u], t2[v]) % (n + 1)
        d = -1
        if not (dist[u] + dist[v]) % 2:
            z.append(u)
            z.append(v)
            d = 1
        dp[u] += d
        dp[v] += d
        dp[w] -= 2 * d
    for i in p[::-1][:-1]:
        j = parent[i]
        dp[j] += dp[i]
    ma = max(dp[2:])
    ans0 = 'YES'
    if 2 * ma == len(z) and ma:
        i = dp[2:].index(ma) + 2
        (_, dist, _) = bfs([i, parent[i]])
    elif len(z) == 2:
        (_, dist, _) = bfs(z)
    elif z:
        ans0 = 'NO'
    ans.append(ans0)
    if ans0 == 'NO':
        continue
    ans1 = [dist[i] & 1 ^ 1 for i in range(1, n + 1)]
    ans.append(''.join(map(str, ans1)))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
out = []
DFS_IN = 0
DFS_OUT = 1

def solve():
    (n, m) = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)
    col = [-1] * n
    level = [0] * n
    dp_good = [0] * n
    dp_bad = [0] * n
    cnt = 0
    flip = 0
    stack = [(0, -1, DFS_IN)]
    while stack:
        (u, par, state) = stack.pop()
        if state == DFS_IN:
            if col[u] != -1:
                continue
            if par == -1:
                col[u] = 0
                level[u] = 1
            else:
                col[u] = 1 - col[par]
                level[u] = level[par] + 1
            stack.append((u, par, DFS_OUT))
            for v in g[u]:
                if col[v] == -1:
                    stack.append((v, u, DFS_IN))
                elif level[v] < level[u] - 1:
                    if col[v] == col[u]:
                        cnt += 1
                        flip = 1 - col[v]
                        dp_bad[u] += 1
                        dp_bad[v] -= 1
                    else:
                        dp_good[u] += 1
                        dp_good[v] -= 1
        else:
            dp_good[par] += dp_good[u]
            dp_bad[par] += dp_bad[u]

    def change_color(u):
        stack = [u]
        while stack:
            u = stack.pop()
            col[u] ^= 1
            for v in g[u]:
                if level[v] == level[u] + 1:
                    stack.append(v)
    if cnt == 1:
        if flip:
            col = [1 - c for c in col]
        out.append('YES')
        out.append(''.join(map(str, col)))
        return
    rmv = -1
    for i in range(n):
        if dp_bad[i] == cnt and dp_good[i] == 0:
            rmv = i
            break
    if rmv == -1:
        out.append('NO')
    else:
        if col[rmv] == 1:
            col = [1 - c for c in col]
        change_color(rmv)
        out.append('YES')
        out.append(''.join(map(str, col)))
for _ in range(int(input())):
    solve()
print('\n'.join(out))

Solution (Python):
input = __import__('sys').stdin.readline
DFS_IN = 0
DFS_OUT = 1

def solve():
    (n, m) = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(lambda x: int(x) - 1, input().split())
        adj[u].append(v)
        adj[v].append(u)
    cnt_odd = 0
    dfs_in = [0] * n
    dfs_out = [0] * n
    depth = [0] * n + [-1]
    color = [-1] * n + [1]
    removed_back_edge = None
    dp = [[0] * 2 for _ in range(n + 1)]
    i = 0
    stack = [(0, -1, DFS_IN)]
    while len(stack) > 0:
        i += 1
        (u, par, state) = stack.pop()
        if state == DFS_IN:
            if color[u] != -1:
                continue
            dfs_in[u] = i
            color[u] = color[par] ^ 1
            depth[u] = depth[par] + 1
            stack.append((u, par, DFS_OUT))
            for v in adj[u]:
                if color[v] == -1:
                    stack.append((v, u, DFS_IN))
                elif depth[v] - depth[u] not in (-1, 1) and depth[u] > depth[v]:
                    if color[u] == color[v]:
                        if removed_back_edge is None:
                            removed_back_edge = (u, v)
                        else:
                            removed_back_edge = (n, n)
                    parity = color[u] ^ color[v] ^ 1
                    dp[u][parity] += 1
                    dp[v][parity] -= 1
                    cnt_odd += parity
        if state == DFS_OUT:
            dfs_out[u] = i
            dp[par][0] += dp[u][0]
            dp[par][1] += dp[u][1]
    color.pop()
    if removed_back_edge is None or removed_back_edge != (n, n):
        xor = 1 if removed_back_edge is not None and (color[removed_back_edge[0]], color[removed_back_edge[1]]) == (0, 0) else 0
        print('YES')
        print(''.join((str(x ^ xor) for x in color)))
        return
    invert_node = next((u for u in range(1, n) if dp[u][1] == cnt_odd and dp[u][0] == 0), None)
    if invert_node is None:
        print('NO')
        return
    xor = color[invert_node]
    xor_subtree = lambda u: dfs_in[invert_node] <= dfs_in[u] <= dfs_out[invert_node]
    print('YES')
    print(''.join((str(x ^ (1 if xor_subtree(u) else 0) ^ xor) for (u, x) in enumerate(color))))
for _ in range(int(input())):
    solve()