Submission #1607288

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class UnionFind
{
    private int[]Par,Rank;
    public UnionFind(int max)
    {
        Par=new int[max];
        Rank=new int[max];
        for(int i=0;i<max;i++)
        {
            Par[i]=i;
        }
    }
    
    private int Find(int n)
    {
        if(Par[n]==n)
        {
            return n;
        }
        else
        {
            return Find(Par[n]);
        }
    }
    
    public bool Same(int a,int b)
    {
        return Find(a)==Find(b);
    }
    
    public void Union(int a,int b)
    {
        a=Find(a);
        b=Find(b);
        if(a==b)return;
        if(Rank[a]<Rank[b])
        {
            Par[a]=b;
        }
        else
        {
            Par[b]=a;
            if(Rank[a]==Rank[b])Rank[a]++;
        }
    }
}

class Program
{
    private int N,M;
    private UnionFind U;
    private void Scan()
    {
        var l=Console.ReadLine().Split(' ');
        N=int.Parse(l[0]);
        M=int.Parse(l[1]);
        U=new UnionFind(N+M);
        for(int i=0;i<N;i++)
        {
            l=Console.ReadLine().Split(' ');
            int k=int.Parse(l[0]);
            for(int j=1;j<=k;j++)
            {
                int lang=int.Parse(l[j])+N-1;
                U.Union(i,lang);
            }
        }
    }
    
    public void Solve()
    {
        Scan();
        for(int i=0;i<N-1;i++)
        {
            if(!U.Same(i,i+1))
            {
                Console.WriteLine("NO");
                return;
            }
        }
        Console.WriteLine("YES");
    } 
    
    static void Main()
    {
        new Program().Solve();
    }
}

Submission Info

Judge Result