Group Division (Codeforces 1916F)
Tags: Greedy, graphs

In the $$$31$$$st lyceum, there were two groups of olympiad participants: computer science and mathematics. The number of computer scientists was $$$n_1$$$, and the number of mathematicians was $$$n_2$$$. It is not known for certain who belonged to which group, but it is known that there were friendly connections between some pairs of people (these connections could exist between a pair of people from the same group or from different groups).The connections were so strong that even if one person is removed along with all their friendly connections, any pair of people still remains acquainted either directly or through mutual friends.$$$^{\dagger}$$$ More formally, two people $$$(x, y)$$$ are acquainted in the following case: there are people $$$a_1, a_2, \ldots,a_n$$$ ($$$1 \le a_i \le n_1 + n_2$$$) such that the following conditions are simultaneously met:$$$\bullet$$$ Person $$$x$$$ is directly acquainted with $$$a_1$$$.$$$\bullet$$$ Person $$$a_n$$$ is directly acquainted with $$$y$$$.$$$\bullet$$$ Person $$$a_i$$$ is directly acquainted with $$$a_{i + 1}$$$ for any ($$$1 \le i \le n - 1$$$).The teachers were dissatisfied with the fact that computer scientists were friends with mathematicians and vice versa, so they decided to divide the students into two groups in such a way that the following two conditions are met:$$$\bullet$$$ There were $$$n_1$$$ people in the computer science group, and $$$n_2$$$ people in the mathematics group.$$$\bullet$$$ Any pair of computer scientists should be acquainted (acquaintance involving mutual friends, who must be from the same group as the people in the pair, is allowed), the same should be true for mathematicians.Help them solve this problem and find out who belongs to which group.

Input: Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then follows the description of the test cases.The first line of each test case contains three integers $$$n_1$$$, $$$n_2$$$, and $$$m$$$ ($$$1 \le n_1, n_2 \le 2000$$$, $$$1 \le m \le 5000$$$). $$$n_1$$$, $$$n_2$$$ are the sizes of the two groups described in the problem, and $$$m$$$ is the number of friendly connections initially.The following $$$m$$$ lines describe the friendly connections: in the $$$i$$$-th ($$$1 \le i \le m$$$) line, a pair of numbers $$$(a, b)$$$ is given, which means that the person with number $$$a$$$ is friends with the person with number $$$b$$$ (and vice versa).It is guaranteed that for each test case, all friendly connections are distinct.It is guaranteed that the sum of $$$n_1 + n_2$$$ for all test cases does not exceed $$$2000$$$, and the sum of $$$m$$$ for all test cases does not exceed $$$5000$$$.It is also guaranteed that for each test case, a solution exists.If there are several answers, print any of them.

Output: For each test case, output two lines.In the first line, output $$$n_1$$$ distinct numbers $$$a_i$$$ ($$$1 \le a_i \le n_1 + n_2$$$) — the people belonging to the first group.In the second line, output $$$n_2$$$ distinct numbers $$$b_i$$$ ($$$1 \le b_i \le n_1 + n_2$$$) — the people belonging to the second group.All numbers must be distinct.If there are several possible answers, print any one.

Note: Consider the third test case. The division into groups looks as follows:    The students selected as computer scientists are colored in green, and those selected as mathematicians are colored in blue.Consider all pairs of computer scientists and how they are acquainted:Pairs $$$(4, 5), (4, 6)$$$ are directly acquainted.Pair $$$(5, 6)$$$ is acquainted through the computer scientist with number $$$4$$$.Consider all pairs of mathematicians and how they are acquainted:Pairs $$$(1, 2), (2, 3)$$$ are directly acquainted.Pair $$$(1, 3)$$$ is acquainted through the mathematician with number $$$2$$$.We conclude that any pair of people belonging to the same group is acquainted with each other, thus the division into two groups is correct.

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

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

Solution (Python):
t = int(input())

def artPointsIter(v0, g, g2):
    stack = [(v0, iter(g[v0]))]
    gtemp = [[] for _ in range(len(g))]
    artv = [0] * len(g)
    assert g2[v0]
    artv[v0] = -1
    tt = 0
    T = [-1] * len(g)
    mT = [0] * len(g)
    while stack:
        (v, it) = stack[-1]
        try:
            u = next(it)
            if g2[u] == False:
                continue
            if T[u] == -1:
                stack.append((u, iter(g[u])))
                tt += 1
                T[u] = tt
                mT[u] = tt
                gtemp[v].append(u)
            else:
                mT[v] = min(mT[v], T[u])
        except StopIteration:
            for u in gtemp[v]:
                if mT[u] >= T[v]:
                    artv[v] = artv[v] + 1
                mT[v] = min(mT[v], mT[u])
            stack.pop()
    return list(map(lambda x: artv[x] > 0, range(len(g))))
for _ in range(t):
    (n1, n2, m) = map(int, input().split(' '))
    swapped = False
    if n1 > n2:
        (n1, n2) = (n2, n1)
        swapped = True
    g = [[] for i in range(n1 + n2)]
    for i in range(m):
        (u, v) = map(lambda x: int(x) - 1, input().split(' '))
        g[u].append(v)
        g[v].append(u)
    g1 = [i == 0 for i in range(n1 + n2)]
    g2 = [i > 0 for i in range(n1 + n2)]
    g2Ac = [False] * (n1 + n2)
    for _ in range(n1 - 1):
        for i in range(n1 + n2):
            g2Ac[i] = False
        for i in range(n1 + n2):
            if g1[i]:
                for j in g[i]:
                    if g2[j]:
                        g2Ac[j] = True
        v0 = 0
        while g2Ac[v0] == False:
            v0 += 1
        art = artPointsIter(v0, g, g2)
        while not g2Ac[v0] or art[v0]:
            v0 += 1
        g1[v0] = True
        g2[v0] = False
    if swapped:
        (g1, g2) = (g2, g1)
    for i in range(n1 + n2):
        if g1[i]:
            print(i + 1, end=' ')
    print()
    for i in range(n1 + n2):
        if g2[i]:
            print(i + 1, end=' ')
    print()

Solution (Python):
t = int(input())
tt = 0

def artPointsIter(v0, g, g2):
    stack = [(v0, iter(g[v0]))]
    gtemp = [[] for _ in range(len(g))]
    artv = [0] * len(g)
    assert g2[v0]
    artv[v0] = -1
    tt = 0
    T = [-1] * len(g)
    mT = [0] * len(g)
    while stack:
        (v, it) = stack[-1]
        try:
            u = next(it)
            if g2[u] == False:
                continue
            if T[u] == -1:
                stack.append((u, iter(g[u])))
                tt += 1
                T[u] = tt
                mT[u] = tt
                gtemp[v].append(u)
            else:
                mT[v] = min(mT[v], T[u])
        except StopIteration:
            for u in gtemp[v]:
                if mT[u] >= T[v]:
                    artv[v] = artv[v] + 1
                mT[v] = min(mT[v], mT[u])
            stack.pop()
    return list(map(lambda x: artv[x] > 0, range(len(g))))
for _ in range(t):
    (n1, n2, m) = map(int, input().split(' '))
    swaped = False
    if n1 > n2:
        (n1, n2) = (n2, n1)
        swaped = True
    g = [[] for i in range(n1 + n2)]
    for i in range(m):
        (u, v) = map(lambda x: int(x) - 1, input().split(' '))
        g[u].append(v)
        g[v].append(u)
    g1 = [i == 0 for i in range(n1 + n2)]
    g2 = [i > 0 for i in range(n1 + n2)]
    g2Ac = [False] * (n1 + n2)
    for _ in range(n1 - 1):
        for i in range(n1 + n2):
            g2Ac[i] = False
        for i in range(n1 + n2):
            if g1[i]:
                for j in g[i]:
                    if g2[j]:
                        g2Ac[j] = True
        v0 = 0
        while g2Ac[v0] == False:
            v0 += 1
        art = artPointsIter(v0, g, g2)
        while not g2Ac[v0] or art[v0]:
            v0 += 1
        g1[v0] = True
        g2[v0] = False
    if swaped:
        (g1, g2) = (g2, g1)
    for i in range(n1 + n2):
        if g1[i]:
            print(i + 1, end=' ')
    print()
    for i in range(n1 + n2):
        if g2[i]:
            print(i + 1, end=' ')
    print()

Solution (Python):
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def solve(N0, N1, M, edge):
    group = [1] * (N0 + N1)
    group[0] = 0

    def connection_check():
        visit = [False] * (N0 + N1)
        root = [group.index(p) for p in range(2)]
        for p in range(2):
            visit[root[p]] = True
            stack = [root[p]]
            while stack:
                v = stack.pop()
                for nv in edge[v]:
                    if group[nv] == p and (not visit[nv]):
                        visit[nv] = True
                        stack.append(nv)
        return all((a for a in visit))
    for _ in range(N1 - 1):
        leaf = False
        for v in range(N0 + N1):
            if group[v] == 1:
                check = 0
                for nv in edge[v]:
                    if group[nv] == 1:
                        check += 1
                if check == 1:
                    group[v] = 0
                    leaf = True
                    break
        if leaf:
            continue
        parent = [-1] * (N0 + N1)
        lowlink = [-1] * (N0 + N1)
        v_ord = [-1] * (N0 + N1)
        child = [0] * (N0 + N1)
        tree_edge = [[] for v in range(N0 + N1)]

        def calc_lowlink(start):
            stack = [(start, -1)]
            nxt_ord = 0
            visited = []
            while stack:
                (v, pv) = stack.pop()
                if v < 0:
                    v = ~v
                    lowlink[v] = v_ord[v]
                    for nv in edge[v]:
                        if nv == parent[v]:
                            continue
                        if group[nv] == 0:
                            continue
                        if v_ord[nv] > v_ord[v]:
                            lowlink[v] = min(lowlink[v], lowlink[nv], v_ord[nv])
                        else:
                            lowlink[v] = min(lowlink[v], v_ord[nv])
                    continue
                if v_ord[v] != -1:
                    continue
                if pv != -1:
                    child[pv] += 1
                    parent[v] = pv
                    tree_edge[pv].append(v)
                v_ord[v] = nxt_ord
                visited.append(v)
                nxt_ord += 1
                stack.append((~v, -1))
                for nv in edge[v]:
                    if group[nv] == 0:
                        continue
                    stack.append((nv, v))
        root = group.index(1)
        calc_lowlink(root)
        for v in range(N0 + N1):
            if group[v] == 0:
                continue
            joint = False
            if v == root:
                if child[v]:
                    joint = True
            else:
                for nv in tree_edge[v]:
                    if nv == parent[v]:
                        continue
                    if group[nv] == 1 and lowlink[nv] >= v_ord[v]:
                        joint = True
            if joint:
                continue
            flg = False
            for nv in edge[v]:
                if group[nv] == 0:
                    group[v] = 0
                    flg = True
            if flg:
                break
    A = [v + 1 for v in range(N0 + N1) if group[v] == 1]
    B = [v + 1 for v in range(N0 + N1) if group[v] == 0]
    assert len(B) == N1
    print(*A)
    print(*B)

def make_random_graph(N0, N1, M):
    N = N0 + N1
    edge = set([(i, i + 1) for i in range(N - 1)] + [(0, N - 1)])
    while len(edge) < M:
        u = random.randint(0, N - 1)
        v = random.randint(0, N - 1)
        if u != v:
            edge.add((min(u, v), max(u, v)))
    res_edge = [[] for v in range(N)]
    for (u, v) in edge:
        res_edge[u].append(v)
        res_edge[v].append(u)
    return res_edge
for _ in range(int(input())):
    (N0, N1, M) = mi()
    edge = [[] for v in range(N0 + N1)]
    for i in range(M):
        (u, v) = mi()
        (u, v) = (u - 1, v - 1)
        edge[u].append(v)
        edge[v].append(u)
    solve(N0, N1, M, edge)