Problem:


Score : 400 points

Problem Statement

On a planet far, far away, M languages are spoken. They are conveniently numbered 1 through M.

For CODE FESTIVAL 20XX held on this planet, N participants gathered from all over the planet.

The i-th (1≦i≦N) participant can speak K_i languages numbered L_{i,1}, L_{i,2}, ..., L_{i,{}K_i}.

Two participants A and B can communicate with each other if and only if one of the following conditions is satisfied:

There exists a language that both A and B can speak.

There exists a participant X that both A and B can communicate with.

Determine whether all N participants can communicate with all other participants.

Constraints

2≦N≦10^5

1≦M≦10^5

1≦K_i≦M

(The sum of all K_i)≦10^5

1≦L_{i,j}≦M

L_{i,1}, L_{i,2}, ..., L_{i,{}K_i} are pairwise distinct.

Partial Score

200 points will be awarded for passing the test set satisfying the following: N≦1000, M≦1000 and (The sum of all K_i)≦1000.

Additional 200 points will be awarded for passing the test set without additional constraints.

Input

The input is given from Standard Input in the following format:

N M
K_1 L_{1,1} L_{1,2} ... L_{1,{}K_1}
K_2 L_{2,1} L_{2,2} ... L_{2,{}K_2}
:
K_N L_{N,1} L_{N,2} ... L_{N,{}K_N}

Output

If all N participants can communicate with all other participants, print YES. Otherwise, print NO.

Sample Input 1

4 6
3 1 2 3
2 4 2
2 4 6
1 6

Sample Output 1

YES

Any two participants can communicate with each other, as follows:

Participants 1 and 2: both can speak language 2.

Participants 2 and 3: both can speak language 4.

Participants 1 and 3: both can communicate with participant 2.

Participants 3 and 4: both can speak language 6.

Participants 2 and 4: both can communicate with participant 3.

Participants 1 and 4: both can communicate with participant 2.

Note that there can be languages spoken by no participant.

Sample Input 2

4 4
2 1 2
2 1 2
1 3
2 4 3

Sample Output 2

NO

For example, participants 1 and 3 cannot communicate with each other.



Sample input:
4 6
3 1 2 3
2 4 2
2 4 6
1 6


Sample output:
YES

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self, start, goal):
        grid = self.grid
        cy, cx = start
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        warp = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i, j) not in move and (i != 0 or j != 0):
                    warp.append((i, j))
        # print(warp)
        d = deque()
        wd = deque()
        self.set(start[1], start[0], 0)
        d.append((0, cx, cy))
        while (d or wd):
            # print(len(d), len(wd))
            if d:
                cc, cx, cy = d.popleft()
            else:
                cc, cx, cy = wd.popleft()
            # print(cc, cx, cy)
            if self.get(cx, cy) < cc:
                continue
            for dx, dy in move:

                nx, ny = dx + cx, dy + cy
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc:
                    self.set(nx, ny, cc)
                    d.append((cc, nx, ny))

            for dx, dy in warp:
                nx, ny = dx + cx, dy + cy
                if nx < 0 or nx > self.w + 1 or ny < 0 or ny > self.h + 1:
                    continue
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc + 1:
                    self.set(nx, ny, cc + 1)
                    wd.append((cc + 1, nx, ny))
        # print(warp)
        # self.show()
        # self.showsomejoin(self.grid)
        ans = self.get(goal[1], goal[0])
        if ans == INF:
            print(-1)
            return
        else:
            print(ans)
            return


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def solve():
    n, m = getList()
    lang = [[] for i in range(m+1)]
    for i in range(n):
        lis = getList()
        for li in lis[1:]:
            # print(li)
            lang[li].append(i)

    uf = UnionFind(n)

    for la in lang:
        if not la:
            continue
        leader = la[0]
        for tgt in la[1:]:
            if not uf.same_check(leader, tgt):
                uf.union(leader, tgt)

    if uf.size[uf.find(1)] == n:
        print("YES")
    else:
        print("NO")

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
class Unionfind():  # Unionfind
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

    def find(self, x):  # グループの根
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # グループの併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x


n, m = map(int, input().split())
lang = [list(map(int, input().split()))[1:] for _ in range(n)]

uf = Unionfind(n + m)
for i, li in enumerate(lang):
    for lij in li:
        uf.union(i, lij - 1 + n)
bool = all(uf.find(0) == uf.find(i) for i in range(1, n))
print('YES' if bool else 'NO')

Submission status: Accepted

Solution code:
class Unionfind():  # Unionfind
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

    def find(self, x):  # グループの根
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # グループの併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self, x, y):  # 同じグループか否か
        return self.find(x) == self.find(y)

    def roots(self):  # 根のリスト
        return [i for i, x in enumerate(self.parents) if x < 0]


n, m = map(int, input().split())
lang = [list(map(int, input().split()))[1:] for _ in range(n)]

uf = Unionfind(n + m)
for i, li in enumerate(lang):
    for lij in li:
        uf.union(i, lij - 1 + n)
bool = all(uf.same(0, i) for i in range(1, n))
print('YES' if bool else 'NO')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def bfs():
    q = deque([0])
    dist = [-1]*(N+M)
    dist[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

N, M = map(int, input().split())
G = [[] for _ in range(N+M)]

for i in range(N):
    KL = list(map(int, input().split()))
    
    for L in KL[1:]:
        G[i].append(L-1+N)
        G[L-1+N].append(i)

dist = bfs()

if -1 in dist[:N]:
    print('NO')
else:
    print('YES')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

(n, m), *LL = [[*map(int,o.split())] for o in open(0)]
UF = UnionFind(n + m)
for e, (k, *L) in enumerate(LL):
    for l in L:
        UF.union(e, l + n - 1)
print("YES" if len([*filter(lambda i: i < n, UF.roots())]) == 1 else "NO")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

(n, m), *LL = [[*map(int,o.split())] for o in open(0)]
UF = UnionFind(n + m)
for e, (k, *L) in enumerate(LL):
    for l in L:
        UF.union(e, l + n - 1)
print("YES" if len([i for i, x in enumerate(UF.parents) if x < 0 and i < n]) == 1 else "NO")

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n, m = ns()
    uf = UnionFind(n + m)

    for _ in range(n):
        a = na()
        for i in range(1, a[0] + 1):
            uf.union(_, n + a[i] - 1)

    flg = True
    for i in range(1, n):
        if not uf.same(i, i - 1):
            flg = False
            break

    print("YES" if flg else "NO")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n, m = ns()
    uf = UnionFind(n + m)

    for _ in range(n):
        a = na()
        for i in range(1, a[0] + 1):
            uf.union(_, n + a[i] - 1)

    flg = True
    for i in range(1, n):
        if not uf.same(i, i - 1):
            flg = False
            break

    print("YES" if flg else "NO")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict
    n, m = map(int, readline().split())
    edge = defaultdict(list)
    for i in range(1, n + 1):
        k, *l = map(int, readline().split())
        edge[i + m].extend(l)
        for x in l:
            edge[x].append(i + m)

    visited = [False] * (n + m + 1)

    que = deque()
    que.append(m + 1)
    visited[0] = True

    while que:
        cur = que.popleft()
        for nx in edge[cur]:
            if not visited[nx]:
                que.append(nx)
                visited[nx] = True

    for i in range(1, n + 1):
        if not visited[m + i]:
            return print("NO")

    return print("YES")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline


class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
        self.u = n

    def root(self, x):
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        self.u -= 1
        return True

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.d[self.root(x)]

    def num_union(self):
        return self.u


N, M = map(int, input().split())
u = UnionFind(N+M)
for i in range(N):
    K, *L = map(int, input().split())
    for l in L:
        l = N-1+l
        u.unite(i, l)

for i in range(N):
    if not u.same(0, i):
        print('NO')
        break
else:
    print('YES')

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    # n: 0-ind, m: 1-ind
    n,m = map(int, input().split())
    ml = [ [] for _ in range(m+1)]
    
    # 0~n-1: people (-1), n~n+m-1: lang (+n-1)
    uf = UnionFind(n+m)

    for i in range(n):
        ll = list(map(int, input().split()))[1:]
        for l in ll:
            uf.union(i,l+n-1)
    
    for i in range(n):
        if not uf.same(0,i):
            print('NO')
            break
    else:
        print('YES')
        


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p, q = q, p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
par = [-1 for i in range(n + m)]
for i in range(n):
    l = list(map(int, input().split()))
    for j in l[1:]:
        unite(i, n + j - 1)
for i in range(n - 1):
    if not same(i, i + 1):
        exit(print("NO"))
print("YES")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]#それぞれの要素の根を再帰的に求める

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def main():
    n, m = map(int, input().split())
    language = [[] for _ in range(m)]
    for i in range(n):
        kl = list(map(int, input().split()))
        for j in range(kl[0]):
            language[kl[j+1]-1].append(i)
    
    union = UnionFind(n)
    for lang in language:
        for i in range(1, len(lang)):
            union.union(lang[0], lang[i])
    
    ans = False
    for v in union.par:
        if v == -n:
            ans = True
    
    if ans:
        print("YES")
    else:
        print("NO")
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())





def main():
	n,m=MI()

	L=[[] for _ in range(m+1)]
	for i in range(1,n+1):
		KL=LI()
		for l in KL[1:]:
			L[l].append(i)
	#print(L)

	UF=UnionFind(n)

	for l in L:
		if len(l)>=2:
			for i,j in zip(l[:-1],l[1:]):
				UF.union(i-1,j-1)
	print("YES" if UF.group_count()==1 else "NO")


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())





def main():
	n,m=MI()

	L=[[] for _ in range(m+1)]
	for i in range(1,n+1):
		KL=LI()
		for l in KL[1:]:
			L[l].append(i)
	#print(L)

	UF=UnionFind(n)

	for l in L:
		if len(l)>=2:
			for i,j in zip(l[:-1],l[1:]):
				UF.union(i-1,j-1)
	print("YES" if UF.group_count()==1 else "NO")
























if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot: return
        if self.size[xroot] <= self.size[yroot]:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

N, M = map(int, input().split())

uf = UnionFind(M)
L = []

for _ in range(N):
    k, *l = map(int, input().split())
    for i in range(1, k):
        uf.unite(l[0] - 1, l[i] - 1)
    L.append(l[0] - 1)

if len(set([uf.find(L[i]) for i in range(N)])) == 1:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]<rank[ry]:
		parent[rx]=ry
	else:
		parent[ry]=rx
		if rank[rx]==rank[ry]:
			rank[rx]+=1
def same(x,y):
	return root(x)==root(y)
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
n,m=map(int,input().split())
parent=list(range(n+m))
rank=[0]*(n+m)
for i in range(n):
	l=list(map(int,input().split()))
	del l[0]
	for x in l:
		unite(n+x-1,i)
for i in range(n-1):
	if root(i)!=root(i+1):
		print("NO")
		exit()
print("YES")

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
lang=[[] for _ in range(m)]
ans=UnionFind(n)
for i in range(n):
    k,*l=list(map(int,input().split()))
    for a in l:
        lang[a-1].append(i)
for l in lang:
    if len(l)>=2:
        for i in range(len(l)):
            ans.union(l[0],l[i])
print('YES' if ans.group_count()==1 else 'NO')

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m=map(int,input().split())
uf=UnionFind(m)
L=[0]*m
for i in range(n):
  A=list(map(int,input().split()))
  for j in range(len(A)-1):
    if j<len(A)-2:
      uf.union(A[j+1]-1,A[j+2]-1)
    L[A[j+1]-1]+=1
LL=[]
for i in range(m):
  if L[i]==0:
    continue
  LL.append(uf.find(i))
if len(set(LL))==1:
  print("YES")
else:
  print("NO")