Babysitting (Codeforces 1903F)
Tags: Others, 2-sat

Theofanis wants to play video games, however he should also take care of his sister. Since Theofanis is a CS major, he found a way to do both. He will install some cameras in his house in order to make sure his sister is okay.His house is an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. His sister likes to play at the edges of the graph, so he has to install a camera to at least one endpoint of every edge of the graph. Theofanis wants to find a vertex cover that maximizes the minimum difference between indices of the chosen nodes.More formally, let $$$a_1, a_2, \ldots, a_k$$$ be a vertex cover of the graph. Let the minimum difference between indices of the chosen nodes be the minimum $$$\lvert a_i - a_j \rvert$$$ (where $$$i \neq j$$$) out of the nodes that you chose. If $$$k = 1$$$ then we assume that the minimum difference between indices of the chosen nodes is $$$n$$$. Can you find the maximum possible minimum difference between indices of the chosen nodes over all vertex covers?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{5}, 1 \le m \le 2 \cdot 10^{5}$$$) — the number of nodes and the number of edges. The $$$i$$$-th of the following $$$m$$$ lines in the test case contains two positive integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$), meaning that there exists an edge between them in the graph. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{5}$$$.It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output: For each test case, print the maximum minimum difference between indices of the chosen nodes over all vertex covers.

Note: In the first test case, we can install cameras at nodes $$$1$$$, $$$3$$$, and $$$7$$$, so the answer is $$$2$$$.  In the second test case, we can install only one camera at node $$$1$$$, so the answer is $$$3$$$.

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

Sample Outputs:
2
3
2

Solution (Python):
def binary_search(f, l, h):
    while l + 1 < h:
        mid = (l + h) // 2
        if f(mid):
            l = mid
        else:
            h = mid
    return l

class RestoreableArray:

    def __init__(s, arr):
        s.arr = arr
        s.edits = dict()

    def __getitem__(s, i):
        return s.arr[i]

    def __setitem__(s, i, v):
        if i not in s.edits:
            s.edits[i] = s.arr[i]
        s.arr[i] = v

    def restore(s):
        for (i, v) in s.edits.items():
            s.arr[i] = v
        s.edits.clear()

    def apply(s):
        s.edits.clear()

def try_substitute(edges, gap, value, Lt, Rt, i, val):
    assert value[i] is None
    value[i] = val
    n = len(edges)
    dfs = [i]
    while dfs:
        i = dfs.pop()
        val = value[i]
        assert val is not None
        if val is False:
            for v in edges[i]:
                if value[v] is False:
                    return False
                if value[v] is None:
                    value[v] = True
                    dfs.append(v)
        elif val is True:
            for (sgn, L) in [(1, Lt), (-1, Rt)]:
                bound = max(min(i + sgn * (gap + 1), n), -1)
                for v in range(i + sgn, bound, sgn):
                    if value[v] is None:
                        L[v] = i
                        dfs.append(v)
                        value[v] = False
                    elif value[v] is True:
                        return False
                    elif value[v] is False:
                        if L[v] is not None:
                            return False
                        L[v] = i
                        value[v] = False
    return True

def can_cover(edges, gap):
    n = len(edges)
    value = RestoreableArray([None for i in range(n)])
    Lt = RestoreableArray([None for i in range(n)])
    Rt = RestoreableArray([None for i in range(n)])
    for i in range(n):
        if value[i] is None:
            for val in [False, True]:
                if try_substitute(edges, gap, value, Lt, Rt, i, val):
                    value.apply()
                    Lt.apply()
                    Rt.apply()
                    break
                else:
                    value.restore()
                    Lt.restore()
                    Rt.restore()
            else:
                return False
    return True

def solve(edges):
    n = len(edges)
    return binary_search(lambda gap: can_cover(edges, gap - 1), 1, n + 1)

def f1903():
    t = int(input())
    for i in range(t):
        (n, m) = [int(x) for x in input().split()]
        edges = [[] for j in range(n)]
        for j in range(m):
            (u, v) = [int(x) for x in input().split()]
            u -= 1
            v -= 1
            edges[u].append(v)
            edges[v].append(u)
        print(solve(edges))
f1903()

Solution (Python):
def binary_search(f, l, h):
    while l + 1 < h:
        mid = (l + h) // 2
        if f(mid):
            l = mid
        else:
            h = mid
    return l

class RestoreableArray:

    def __init__(s, arr):
        s.arr = arr
        s.orig = [True] * len(s.arr)
        s.todo = []

    def __getitem__(s, i):
        return s.arr[i]

    def __setitem__(s, i, v):
        if s.orig[i]:
            s.orig[i] = False
            s.todo.append((i, s.arr[i]))
        s.arr[i] = v

    def restore(s):
        for (i, v) in s.todo:
            s.arr[i] = v
            s.orig[i] = True
        s.todo.clear()

    def apply(s):
        for (i, v) in s.todo:
            s.orig[i] = True
        s.todo.clear()

def try_substitute(edges, gap, value, Lt, Rt, i, val):
    assert value[i] is None
    value[i] = val
    n = len(edges)
    dfs = [i]
    while dfs:
        i = dfs.pop()
        val = value[i]
        assert val is not None
        if val is False:
            for v in edges[i]:
                if value[v] is False:
                    return False
                if value[v] is None:
                    value[v] = True
                    dfs.append(v)
        elif val is True:
            for (sgn, L) in [(1, Lt), (-1, Rt)]:
                bound = max(min(i + sgn * (gap + 1), n), -1)
                for v in range(i + sgn, bound, sgn):
                    if value[v] is None:
                        L[v] = i
                        dfs.append(v)
                        value[v] = False
                    elif value[v] is True:
                        return False
                    elif value[v] is False:
                        if L[v] is not None:
                            return False
                        L[v] = i
                        value[v] = False
    return True

def can_cover(edges, gap):
    n = len(edges)
    value = RestoreableArray([None for i in range(n)])
    Lt = RestoreableArray([None for i in range(n)])
    Rt = RestoreableArray([None for i in range(n)])
    for i in range(n):
        if value[i] is None:
            for val in [False, True]:
                if try_substitute(edges, gap, value, Lt, Rt, i, val):
                    value.apply()
                    Lt.apply()
                    Rt.apply()
                    break
                else:
                    value.restore()
                    Lt.restore()
                    Rt.restore()
            else:
                return False
    return True

def solve(edges):
    n = len(edges)
    return binary_search(lambda gap: can_cover(edges, gap - 1), 1, n + 1)

def f1903():
    t = int(input())
    for i in range(t):
        (n, m) = [int(x) for x in input().split()]
        edges = [[] for j in range(n)]
        for j in range(m):
            (u, v) = [int(x) for x in input().split()]
            u -= 1
            v -= 1
            edges[u].append(v)
            edges[v].append(u)
        print(solve(edges))
f1903()

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

def f(u, v):
    return u << 20 ^ v

def get_segment(s, t):
    (s, t) = (s + l1, t + l1)
    ans = []
    while s <= t:
        if s & 1:
            ans.append(s)
            s += 1
        s >>= 1
        if not t & 1:
            ans.append(t)
            t -= 1
        t >>= 1
    return ans

def add_edge(u, v, tu, tv, i):
    e[i] = f(u if not tu else u + n, v + n if not tv else v)
    e[i + 1] = f(v if not tv else v + n, u + n if not tu else u)
    return

def make_graph(n, m):
    for i in range(n + 3):
        s1[i] = s2[i] = 0
    for i in range(m):
        (u, v) = (e[i] >> 20, e[i] & 1048575)
        s1[u + 2] += 1
        s2[v + 2] += 1
    for i in range(3, n + 3):
        s1[i] += s1[i - 1]
        s2[i] += s2[i - 1]
    for i in range(m):
        (u, v) = (e[i] >> 20, e[i] & 1048575)
        G[s1[u + 1]] = G[s1[u + 1]] & 1099510579200 ^ v
        G[s2[v + 1]] = G[s2[v + 1]] & 1048575 ^ u << 20
        s1[u + 1] += 1
        s2[v + 1] += 1
    return (s1, s2)

def scc(n, s1, s2):
    now = list(s1)
    st = []
    u = [0] * (2 * n + 1)
    c = 1
    for i in range(1, 2 * n + 1):
        if u[i]:
            continue
        (st, u[i]) = ([i], -1)
        while st:
            j = st[-1]
            while now[j] < s1[j + 1] and u[G[now[j]] & 1048575]:
                now[j] += 1
            if now[j] == s1[j + 1]:
                u[st.pop()] = c
                c += 1
            else:
                st.append(G[now[j]] & 1048575)
                u[st[-1]] = -1
    v = [0] * (2 * n)
    for i in range(1, 2 * n + 1):
        v[u[i] - 1] = i
    (z, z0) = (1 << 20, 1 << 20)
    for i in v[::-1]:
        if u[i] & z0:
            continue
        (q, u[i]) = ([i], z)
        for j in q:
            if j <= n and u[j + n] == z or (j > n and u[j - n] == z):
                return False
            for w in range(s2[j], s2[j + 1]):
                k = G[w] >> 20
                if not u[k] & z0:
                    q.append(k)
                    u[k] = z0
        z += 1
    return True

def two_sat(n, m):
    make_graph(2 * n, m)
    return scc(n, s1, s2)

def binary_search(c1, c2):
    c = (c1 + c2 + 1) // 2
    while abs(c1 - c2) > 1:
        c = (c1 + c2 + 1) // 2
        if ok(c):
            c1 = c
        else:
            c2 = c
    while not ok(c):
        c -= 1
    return c

def ok(c):
    if c <= 1:
        return True
    elif c > n0:
        return False
    m = 2 * m0
    for i in range(1, n0 + 1):
        (s, t) = (max(i - c + 1, 1) + l1, i - 1 + l1)
        while s <= t:
            if s & 1:
                add_edge(i + l1, s, 1, 1, m)
                m += 2
                s += 1
            s >>= 1
            if not t & 1:
                add_edge(i + l1, t, 1, 1, m)
                m += 2
                t -= 1
            t >>= 1
    return True if two_sat(n, m) else False
t = int(input())
ans = []
e = [0] * 6000000
G = [0] * 6000000
for _ in range(t):
    (n, m) = map(int, input().split())
    l1 = pow(2, (n + 1).bit_length())
    l2 = 2 * l1
    (n0, m0) = (n, 0)
    n += l1
    (s1, s2) = ([0] * (2 * n + 3), [0] * (2 * n + 3))
    for _ in range(m):
        (u, v) = map(int, input().split())
        add_edge(u + l1, v + l1, 0, 0, 2 * m0)
        m0 += 1
    for i in range(1, l1):
        if i << 1 <= l1 + n0:
            add_edge(i << 1, i, 1, 0, 2 * m0)
            m0 += 1
        if i << 1 ^ 1 <= l1 + n0:
            add_edge(i << 1 ^ 1, i, 1, 0, 2 * m0)
            m0 += 1
    ans0 = binary_search(1, n0 + 1)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))