Edge Split (Codeforces 1726D)
Tags: Others, probabilities

You are given a connected, undirected and unweighted graph with $$$n$$$ vertices and $$$m$$$ edges. Notice the limit on the number of edges: $$$m \le n + 2$$$.Let's say we color some of the edges red and the remaining edges blue. Now consider only the red edges and count the number of connected components in the graph. Let this value be $$$c_1$$$. Similarly, consider only the blue edges and count the number of connected components in the graph. Let this value be $$$c_2$$$.Find an assignment of colors to the edges such that the quantity $$$c_1+c_2$$$ is minimised.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n-1 \leq m \leq \min{\left(n+2,\frac{n \cdot (n-1)}{2}\right)}$$$) — the number of vertices and the number of edges respectively.$$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$) denoting that the $$$i$$$-th edge goes between vertices $$$u_i$$$ and $$$v_i$$$. The input is guaranteed to have no multiple edges or self loops. The graph is also guaranteed to be connected.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$. It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^6$$$.

Output: For each test case, output a binary string of length $$$m$$$. The $$$i$$$-th character of the string should be 1 if the $$$i$$$-th edge should be colored red, and 0 if it should be colored blue. If there are multiple ways to assign colors to edges that give the minimum answer, you may output any.

Note:  The corresponding graph of the first test case is:  $$$c_1 + c_2 = 1 + 2 = 3$$$ The corresponding graph of the second test case is:  $$$c_1 + c_2 = 2 + 2 = 4$$$

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

Sample Outputs:
0111010
1001
0001111
0

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def find_root(root_dict, x):
    L = []
    while x != root_dict[x]:
        L.append(x)
        x = root_dict[x]
    for y in L:
        root_dict[y] = x
    return x

def process(n, G):
    m = len(G)
    answer = [None for i in range(m)]
    root_dict = [i for i in range(n + 1)]
    good_edges = []
    bad_edges = []
    for i in range(m):
        (u, v) = G[i]
        u1 = find_root(root_dict, u)
        v1 = find_root(root_dict, v)
        if u1 != v1:
            good_edges.append([u, v, i])
            root_dict[u1] = v1
            answer[i] = '0'
        else:
            bad_edges.append([u, v, i])
            answer[i] = '1'
    if len(bad_edges) == 3:
        (u1, v1, i1) = bad_edges[0]
        (u2, v2, i2) = bad_edges[1]
        (u3, v3, i3) = bad_edges[2]
        L = [u1, v1, u2, v2, u3, v3]
        L = sorted(L)
        if L[0] == L[1] and L[2] == L[3] and (L[4] == L[5]):
            answer[i3] = '0'
            root_dict = [i for i in range(n + 1)]
            root_dict[u3] = v3
            for (u, v, i) in good_edges:
                u1 = find_root(root_dict, u)
                v1 = find_root(root_dict, v)
                if u1 == v1:
                    answer[i] = '1'
                    break
                else:
                    root_dict[u1] = v1
    answer = ''.join(answer)
    sys.stdout.write(f'{answer}\n')
    return
t = int(input())
for i in range(t):
    (n, m) = [int(x) for x in input().split()]
    G = []
    for j in range(m):
        (u, v) = [int(x) for x in input().split()]
        G.append([u, v])
    process(n, G)

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

def unionfind(group, root):
    son = root
    while root != group[root]:
        root = group[root]
    while son != root:
        temp = group[son]
        group[son] = root
        son = group[temp]
    return root

def getpath(start, end, neigh):
    n = len(neigh)
    pre = [-1] * n
    queue = deque()
    visited = [False] * n
    visited[start] = True
    queue.append(start)
    while queue:
        index = queue.popleft()
        for (nextindex, enum) in neigh[index]:
            if visited[nextindex]:
                continue
            visited[nextindex] = True
            pre[nextindex] = index
            queue.append(nextindex)
            if nextindex == end:
                return enum

def main(t):
    (n, m) = map(int, input().split())
    ans = []
    group = [i for i in range(n)]
    neigh = [[] for _ in range(n)]
    edges = []
    extra = []
    for i in range(m):
        (u, v) = map(int, input().split())
        u -= 1
        v -= 1
        edges.append([u, v])
        root1 = unionfind(group, u)
        root2 = unionfind(group, v)
        if root1 == root2:
            ans.append('1')
            extra.append(i)
        else:
            group[max(root1, root2)] = min(root1, root2)
            ans.append('0')
            neigh[u].append((v, i))
            neigh[v].append((u, i))
    if len(extra) == 3:
        collect = set()
        for d in range(3):
            collect.add(edges[extra[d]][0])
            collect.add(edges[extra[d]][1])
        if len(collect) == 3:
            replace = getpath(edges[extra[0]][0], edges[extra[0]][1], neigh)
            ans[replace] = '1'
            ans[extra[0]] = '0'
    ans = ''.join(ans)
    sys.stdout.write(ans + '\n')
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
class UnionFind:

    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            (self.parent[acopy], acopy) = (a, self.parent[acopy])
        return a

    def union(self, a, b):
        self.parent[self.find(b)] = self.find(a)

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m) = readIntArr()
        adj = [[] for _ in range(n)]
        edges = []
        for i in range(m):
            (u, v) = readIntArr()
            u -= 1
            v -= 1
            adj[u].append((v, i))
            adj[v].append((u, i))
            edges.append((u, v))
        ans = [-1] * m
        uf = UnionFind(n)
        blue_nodes = []
        blue_edges = []
        for (e, (u, v)) in enumerate(edges):
            if uf.find(u) != uf.find(v):
                uf.union(u, v)
                ans[e] = 1
            else:
                ans[e] = 0
                blue_nodes.append(u)
                blue_nodes.append(v)
                blue_edges.append(e)
        if len(set(blue_nodes)) == 3:
            blue_edge = blue_edges[0]
            (bn1, bn2) = edges[blue_edge]
            for node in blue_nodes:
                if node != bn1 and node != bn2:
                    bn3 = node
            vi = [0] * n
            st = [bn1]
            vi[bn1] = 1
            red_edge = -1
            while st:
                u = st.pop()
                for (v, e) in adj[u]:
                    if e in blue_edges:
                        continue
                    if vi[v] == 0:
                        vi[v] = 1
                        st.append(v)
                        if v == bn2:
                            red_edge = e
                            break
                if red_edge != -1:
                    break
            assert red_edge != -1
            ans[blue_edge] = 1
            ans[red_edge] = 0
        s = ''.join([str(x) for x in ans])
        allans.append(s)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()