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: Runtime Error

Solution code:
N,M = map(int,input().split())
L = []
for i in range(N):
  tmp = list(map(int,input().split()))
  L.append(tmp[1:])

dicL = {}
for i in range(N):
  for l in L[i]:
    if l not in dicL:
      dicL[l] = [i]
    else:
      dicL[l].append(i)
#print(dicL)
E = [[] for _ in range(N)]
for k,v in dicL.items():
  if len(v) > 1:
    for i in range(len(v)-1):
      for j in range(i+1,len(v)):
        E[v[i]].append(v[j])
        E[v[j]].append(v[i])
for i in range(N):
  E[i] = set(E[i])
#print(E)
Visited = [0 for _ in range(N)]
def dfs(v):
  Visited[v] = 1
  for u in E[v]:
    if Visited[u] == 0:
      dfs(u)
dfs(0)
print('YES' if sum(Visited) == N else 'NO')

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m=map(int,input().split())
kl=[list(map(int,input().split())) for i in range(n)]
uf=UnionFind(m)
for i in range(n):
    for j in range(2,kl[i][0]+1):    
        uf.union(kl[i][1], kl[i][j])

flag=uf.par[1]
for i in range(2,n):
    if flag!=uf.par[i]:
        print("NO")
        quit()
print("YES")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n):
    t=(list(map(int,input().split())))
    l.append(set(t[1:]))
#print(l)
lll=[]
for i in range(n):
    ll={}
    for j in range(i+1,n):
        if set(l[i])&set(l[j]):
            ll=set(ll)|set(l[i])|set(l[j])
    lll.append(ll)
lll=lll[:-1]
#print(lll)
l_l={}
for i in range(n-1):
    for j in range(i+1,n-1):
        if set(l[i])&set(l[j]):
            l_l=set(l_l)|set(l[i])|set(l[j])
#print(l_l)
count=0
for i in range(n):
    if l[i]&l_l:
        count+=1
if count==n:
    print('YES')
else:
    print('NO')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
L = []
for i in range(N):
  Ls = list(map(int, input().split()))
  Ls.pop(0)
  Ls = [l-1 for l in Ls]
  L.append(Ls)
#print(L)
UF = list(range(N+M))
def par(m):
  if UF[m] == m:
    return m
  r = par(UF[m])
  UF[m] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[j] = i
for i in range(N):
  Ls = L[i]
  for l in Ls:
    unite(i, N+l)
for i in range(N+M):
  p = par(i)
#print(UF)
ok = True
for i in range(1, N):
  if par(i) != par(i-1):
    ok = False
    break
if ok:
  print("YES")
else:
  print("NO")

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
L = []
S = [[] for i in range(M)]
for i in range(N):
  Ls = list(map(int, input().split()))
  Ls.pop(0)
  Ls = [l-1 for l in Ls]
  L.append(Ls)
  for l in Ls:
    S[l].append(i)
#print(L)
#print(S)
UF = list(range(N+M))
def par(m):
  if UF[m] == m:
    return m
  r = par(UF[m])
  UF[m] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[j] = i
for i in range(N):
  Ls = L[i]
  for l in Ls:
    unite(i, N+l)
ok = True
for i in range(1, N):
  if par(i) != par(i-1):
    ok = False
    break
if ok:
  print("YES")
else:
  print("NO")

Submission status: Runtime Error

Solution code:
import collections

n, m = map(int, input().split())
d = [set() for _ in range(m)] # key=言語 val=利用者一覧
for i in range(n):
    line = list(map(int, input().split()))
    for l in line[1:]:
        d[l - 1].add(i)

s = set(d[0])
for i in range(1, n):
    if s & d[i]:
        s |= d[i]
    else:
        print('NO')
        exit()

print('YES')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
N,M = map(int,input().split())
R = [[] for _ in range(N+M)]
for i in range(N):
    L = list(map(lambda x:int(x)-1+N,input().split()))[1:]
    R[i]+=L
    for l in L:
        R[l].append(i)
A = [0]*(N+M)
def f(v):
    global R,A
    A[v] = 1
    for c in R[v]:
        if c<N and A[c]==1: continue
        f(c)
f(0)
print("YES" if sum(L[:N])==N else "NO")

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
R = [[] for _ in range(N+M)]
for i in range(N):
    L = list(map(lambda x:int(x)-1+N,input().split()))[1:]
    R[i]+=L
    for l in L:
        R[l].append(i)
A = [0]*(N+M)
def f(v):
    global R,A
    A[v] = 1
    for c in R[v]:
        if c<N and A[c]==1: continue
        f(c)
f(0)
print("YES" if sum(L[:N])==N else "NO")

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(N)]
import sys
sys.setrecursionlimit(10**5)
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(M)
used=[0]*M
for x,*l in L:
    used[l[0]-1]=1
    for i in range(x-1):
        used[l[i+1]-1]=1
        u.unite(l[i]-1,l[i+1]-1)
print(['NO','YES'][u.size(L[0][1])==sum(used)])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(N)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(M)
used=[0]*M
for _,*l in L:
    used[l[0]-1]=1
    for i in range(len(l)-1):
        used[l[i+1]-1]=1
        u.unite(l[i]-1,l[i+1]-1)
print(['NO','YES'][u.size(L[0][1])==sum(used)])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range((n+m))]
for i in range(n):
    a=[int(i)-1 for i in input().split()][1:]
    for l in a:
        g[i].append(n+l)
        g[n+l].append(i)

par=[i for i in range(n+m)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
        
def connect(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        0
    else:
        par[rx]=ry
    return

for i in range(n+m):
    for nb in g[i]:
        connect(i,nb)

p=par[0]
ans='YES'
for i in range(n):
    if par[i]!=p:
        ans='NO'

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range((n+m))]
for i in range(n):
    a=[int(i)-1 for i in input().split()][1:]
    for l in a:
        g[i].append(l)
        g[n+l].append(i)

par=[i for i in range(n+m)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
        
def connect(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        0
    else:
        par[rx]=ry
    return

for i in range(n+m):
    for nb in g[i]:
        connect(i,nb)

p=par[0]
ans='YES'
for i in range(n):
    if par[i]!=p:
        ans='NO'

print(ans)

Submission status: Runtime Error

Solution code:
#include<iostream>

#include <vector>
#include <list>
#include<stack>
#include<queue>
#include<array>

#include <set>
#include<map>

#include<string>
#include<stdlib.h>
#include<memory>

#include<algorithm>
#include <functional>
#include<math.h>

#include<fstream>
#include<iomanip>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7


class UnionFind {
public:
	vector<int>rank, parent;
	//������
	UnionFind(int size) {
		rank.resize(size, 0);
		parent.resize(size, 0);
		REP(i, size)parent[i] = i;
	}
	//�؂̍������߂�
	int find(int x) {
		if(parent[x] == x)return x;
		else return parent[x] = find(parent[x]);
	}
	//x��y�̑�����W���𕹍�
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if(x == y)return;
		if(rank[x] < rank[y])
			parent[x] = y;
		else {
			parent[y] = x;
			if(rank[x] == rank[y])rank[x]++;
		}
	}
	//x��y�������W���ɑ����邩�ۂ�
	bool same(int x, int y) {
		return (find(x) == find(y));
	}
	//parent�̓��e���o��
	void debug() {
		for(auto num : parent) {
			cout << num << " ";
		}
		cout << "more:" << endl;
		REP(i, parent.size()) {
			cout << find(i) << " ";

		}
		cout << endl << "more:" << endl;
		for(auto num : parent) {
			cout << num << " ";
		}
		cout << endl;
	}
};


//�ϐ�
int N,M;
vector<vector<int>> L;





//�T�u�֐�
//����
void input()
{
	cin>>N>>M;
	L.resize(N);
	int k;
	REP(i, N)
	{
		cin>>k;
		L[i].resize(k);
		REP(j,k)cin>>L[i][j];
	}
}


//�v�Z
void calc()
{
	UnionFind uf(N);
	map<int,vector<int>> mp;
	REP(i, N)
	{
		for(auto num : L[i])
		{
			mp[num].push_back(i);
		}
	}

	for(auto itr = mp.begin(); itr != mp.end(); ++itr)
	{
		auto v = itr->second;
		if(v.size() > 1)
		{
			REP(i, (int)(v.size() - 1))
			{
				uf.unite(v[i],v.back());
			}
		}
	}
	
	REP(i, N-1)
	{
		if(!uf.same(i, N - 1))
		{
			cout<<"NO"<<endl;
			return;
		}
	}
	cout << "YES"<<endl;
}


//�o��
void output()
{

}


//�f�o�b�O
void debug()
{
    int N;
    cin>>N;
}


//���C���֐�
int main()
{
    input();
    calc();
    output();
    debug();
    
    return 0;
}

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
f=lambda x:int(x)-1

langs=[[] for _ in range(m)]
speakers=[[] for _ in range(n)]
used_langs=[False]*m
used_speakers=[False]*n

for i in range(n):
  *l,=map(f,input().split()[1:])
  speakers[i].extend(l)
  for j in l:
    langs[j].append(i)

def dfs(n):
  if used_speakers[n]:
    return
  used_speakers[n]=True
  for i in speakers[n]:
    if used_langs[i]:continue
    used_langs[i]=True
    for j in langs[i]:
      dfs(j)

dfs(0)
if not False in used_speakers:
  print("YES")
else:
  print("NO")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

L = [list(map(int, input().split()))[1:] for _ in range(N)]

g = [[] for _ in range(200005)]

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N)
        g[N+ll].append(i)
used = [False] * 200005

def is_connected(v):
    if used[v]:
        return
    used[v] = True

    for next_v in g[v]:
        is_connected(next_v)

is_connected(0)

if all(used[:N]):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

L = [list(map(int, input().split()))[1:] for _ in range(N)]

g = [[] for _ in range(200005)]

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N)
        g[N+ll].append(i)
used = [False] * 200005

def is_connected(v):
    if used[v]:
        return
    used[v] = True

    for next_v in g[v]:
        is_connected(next_v)

is_connected(0, -1)

if all(used):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

L = [list(map(int, input().split()))[1:] for _ in range(N)]

g = [[] for _ in range(N+M+1)]

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N)
        g[N+ll].append(i)
used = [False] * 200005

def is_connected(v):
    if used[v]:
        return
    used[v] = True

    for next_v in g[v]:
        is_connected(next_v)

is_connected(0, -1)

if all(used):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

L = [list(map(int, input().split()))[1:] for _ in range(N)]

g = [[] for _ in range(N+M+1)]

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N)
        g[N+ll].append(i)
used = [False] * (200005)

def is_connected(v):
    if used[v]:
        return
    used[v] = True

    for next_v in g[v]:
        is_connected(next_v)

is_connected(0, -1)

if all(used):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

L = [list(map(int, input().split()))[1:] for _ in range(N)]

g = [[] for _ in range(N+K)]

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N-1)
        g[N+ll-1].append(i)
used = [False] * N

def is_connected(v, prev):
    if 0 <= v < N and used[v]:
        return
    elif 0 <= v < N:
        used[v] = True

    for next_v in g[v]:
        if next_v == prev:
            continue
        is_connected(next_v, v)
    return

is_connected(0, -1)

if all(used):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

L = [list(map(int, input().split()))[1:] for _ in range(N)]

g = [[] for _ in range(N+M+100)]

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N-1)
        g[N+ll-1].append(i)
used = [False] * N

def is_connected(v, prev):
    if 0 <= v < N and used[v]:
        return
    elif 0 <= v < N:
        used[v] = True

    for next_v in g[v]:
        if next_v == prev:
            continue
        is_connected(next_v, v)
    return

is_connected(0, -1)

if all(used):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

# if N > 1000 and M > 1000:
#     print("YES")
#     sys.exit()

L = [list(map(int, input().split()))[1:] for _ in range(N)]

g = [[] for _ in range(N+M)]

for i, l in enumerate(L):
    for ll in l:
        g[i].append(ll+N-1)
        g[N+ll-1].append(i)
# print(g)
used = [False] * N

def is_connected(v, prev):
    if 0 <= v < N and used[v]:
        return
    elif 0 <= v < N:
        # print(v, prev)
        used[v] = True

    for next_v in g[v]:
        if next_v == prev:
            continue
        is_connected(next_v, v)
    return

is_connected(0, -1)

if all(used):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
# coding: utf-8

import collections

def dfs(i):
    if visited[i] == 1:
        return
    visited[i] = 1
    for j in speakers[i]:
        for k in langs[j]:
            dfs(k)


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

langs = collections.defaultdict(list)
speakers = [[] for _ in range(N)]

for i in range(N):
    ls = list(map(int, input().split()))
    for j in range(1, ls[0] + 1):
        langs[ls[j]-1].append(i)
        speakers[i].append(ls[j]-1)

visited = [0] * N
dfs(0)

if 0 not in visited:
    print("YES")
else:
    print("NO")