Split Into Two Sets (Codeforces 1702E)
Tags: Others, dsu

Polycarp was recently given a set of $$$n$$$ (number $$$n$$$ — even) dominoes. Each domino contains two integers from $$$1$$$ to $$$n$$$.Can he divide all the dominoes into two sets so that all the numbers on the dominoes of each set are different? Each domino must go into exactly one of the two sets.For example, if he has $$$4$$$ dominoes: $$$\{1, 4\}$$$, $$$\{1, 3\}$$$, $$$\{3, 2\}$$$ and $$$\{4, 2\}$$$, then Polycarp will be able to divide them into two sets in the required way. The first set can include the first and third dominoes ($$$\{1, 4\}$$$ and $$$\{3, 2\}$$$), and the second set — the second and fourth ones ($$$\{1, 3\}$$$ and $$$\{4, 2\}$$$).

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The descriptions of the test cases follow.The first line of each test case contains a single even integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of dominoes.The next $$$n$$$ lines contain pairs of numbers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) describing the numbers on the $$$i$$$-th domino.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case print:  YES, if it is possible to divide $$$n$$$ dominoes into two sets so that the numbers on the dominoes of each set are different;  NO if this is not possible. You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer).

Note: In the first test case, the dominoes can be divided as follows:   First set of dominoes: $$$[\{1, 2\}, \{4, 3\}]$$$  Second set of dominoes: $$$[\{2, 1\}, \{3, 4\}]$$$  In other words, in the first set we take dominoes with numbers $$$1$$$ and $$$2$$$, and in the second set we take dominoes with numbers $$$3$$$ and $$$4$$$.In the second test case, there's no way to divide dominoes into $$$2$$$ sets, at least one of them will contain repeated number.

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

Sample Outputs:
YES
NO
NO
YES
YES
NO

Solution (Python):
import sys
input = lambda : sys.stdin.readline()
_0x3f = lambda : list(map(int, input().split()))

def solve():
    n = int(input())
    g = [[] for _ in range(n)]
    fault = False
    for i in range(n):
        (a, b) = _0x3f()
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)
        if a == b:
            fault = True
    if fault:
        return False
    for i in range(n):
        if len(g[i]) != 2:
            return False
    vis = set()

    def bfs(x):
        t = x
        res = 0
        while True:
            res += 1
            vis.add(t)
            t = g[t][0] if g[t][0] not in vis else g[t][1]
            if t in vis:
                break
        return res
    for i in range(n):
        if i not in vis and bfs(i) % 2:
            return False
    return True
t = int(input())
for _ in range(t):
    print('YES' if solve() else 'NO')

Solution (Python):
def check(g, vis, color, vertex):
    stack = [(vertex, color)]
    while stack:
        (vertex, color) = stack.pop()
        if vis[vertex] != 0:
            if vis[vertex] != color:
                return False
            continue
        vis[vertex] = color
        for child in g[vertex]:
            stack.append((child, -color))
    return True

def cf1702E():
    n = int(input())
    g = [[] for _ in range(n + 1)]
    for i in range(n):
        (u, v) = map(int, input().split())
        g[u].append(v)
        g[v].append(u)
    for i in range(1, n + 1):
        if len(g[i]) >= 3:
            print('NO')
            return
    vis = [0] * (n + 1)
    for i in range(1, n + 1):
        if vis[i] == 0:
            if check(g, vis, 1, i):
                pass
            else:
                print('NO')
                return
    print('YES')
    return
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        cf1702E()

Solution (Python):
def bipartite(g, vis, n, vertex):
    stack = [(vertex, n)]
    while stack:
        (vertex, color) = stack.pop()
        if vis[vertex] != 0:
            if vis[vertex] != color:
                return False
            continue
        vis[vertex] = color
        for child in g[vertex]:
            stack.append((child, -color))
    return True

def solve():
    n = int(input())
    adj = {i: [] for i in range(1, n + 1)}
    mp = {}
    for i in range(n):
        (u, v) = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    for i in range(1, n + 1):
        if len(adj[i]) >= 3:
            print('NO')
            return
    vis = [0] * (n + 1)
    for i in range(1, n + 1):
        if vis[i] == 0:
            if bipartite(adj, vis, 1, i):
                pass
            else:
                print('NO')
                return
    print('YES')
    return
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()