Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(20000)


def _ia(): return map(int, sys.stdin.readline().strip().split())


class UnionFind:
    def __init__(self, n):
        self._par = [-1]*(n+1)
        self._rnk = [0]*(n+1)

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        elif self._rnk[x] > self._rnk[y]:
            self._par[x] += self._par[y]
            self._par[y] = x
        else:
            self._par[y] += self._par[x]
            self._par[x] = y
            if self._rnk[x] == self._rnk[y]:
                self._rnk[y] += 1

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


def main():
    n, m = _ia()
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: x-1, _ia())
        uf.unite(a, b)
    c = Counter([uf.root(i) for i in range(n)])
    return max(c.values())


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
#    Copyright 2016-2019 NetworkX developers.
#    Copyright (C) 2004-2019 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
"""
Union-find data structure.
"""

from networkx.utils import groups


class UnionFind:
    """Union-find data structure.

    Each unionFind instance X maintains a family of disjoint sets of
    hashable objects, supporting the following two methods:

    - X[item] returns a name for the set containing the given item.
      Each set is named by an arbitrarily-chosen one of its members; as
      long as the set remains unchanged it will keep the same name. If
      the item is not yet part of a set in X, a new singleton set is
      created for it.

    - X.union(item1, item2, ...) merges the sets containing each item
      into a single larger set.  If any item is not yet part of a set
      in X, it is added to X as one of the members of the merged set.

      Union-find data structure. Based on Josiah Carlson's code,
      http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
      with significant additional changes by D. Eppstein.
      http://www.ics.uci.edu/~eppstein/PADS/UnionFind.py

    """

    def __init__(self, elements=None):
        """Create a new empty union-find structure.

        If *elements* is an iterable, this structure will be initialized
        with the discrete partition on the given set of elements.

        """
        if elements is None:
            elements = ()
        self.parents = {}
        self.weights = {}
        for x in elements:
            self.weights[x] = 1
            self.parents[x] = x

    def __getitem__(self, object):
        """Find and return the name of the set containing the object."""

        # check for previously unknown object
        if object not in self.parents:
            self.parents[object] = object
            self.weights[object] = 1
            return object

        # find path of objects leading to the root
        path = [object]
        root = self.parents[object]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]

        # compress the path and return
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def __iter__(self):
        """Iterate through all items ever found or unioned by this structure.

        """
        return iter(self.parents)

    def to_sets(self):
        """Iterates over the sets stored in this structure.

        For example::

            >>> partition = UnionFind('xyz')
            >>> sorted(map(sorted, partition.to_sets()))
            [['x'], ['y'], ['z']]
            >>> partition.union('x', 'y')
            >>> sorted(map(sorted, partition.to_sets()))
            [['x', 'y'], ['z']]

        """
        # Ensure fully pruned paths
        for x in self.parents.keys():
            _ = self[x]  # Evaluated for side-effect only

        # TODO In Python 3.3+, this should be `yield from ...`.
        for block in groups(self.parents).values():
            yield block

    def union(self, *objects):
        """Find the sets containing the objects and merge them all."""
        roots = [self[x] for x in objects]
        # Find the heaviest root according to its weight.
        heaviest = max(roots, key=lambda r: self.weights[r])
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    u = UnionFind(range(1, N + 1))

    for a, b in AB:
        u.union(a, b)

    li = list(u.to_sets())

    ans = 0
    for p in li:
        if len(p) > ans:
            ans = len(p)
    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(s) for s in input().split()]
edge = [[int(s) - 1 for s in input().split()] for _ in range(M)]
graph = [[] for _ in range(N)]

for i, j in edge:
    graph[i].append(j)
    graph[j].append(i)

group = [0] * N
group_num = 0
visited = [False] * N

group_nums = [0] * N

for i in range(N):
    if visited[i]:
        continue
    dq = deque([i])
    group[i] = group_num
    visited[i] = True
    group_nums[group_num] += 1
    while(dq):
        search_obj = dq.pop()
        for candidate_obj in graph[search_obj]:
            if not visited[candidate_obj]:
                group[candidate_obj] = group_num
                dq.appendleft(candidate_obj)
                visited[candidate_obj] = True
                group_nums[group_num] += 1
    group_num += 1

print(max(group_nums))

Submission status: Accepted

Solution code:
import sys
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
 
 
if __name__ == '__main__':
    sys.setrecursionlimit(1000000)
    n,m=map(int,sys.stdin.readline().split())
    ins = UnionFind(n+1)
    for i in range(m):
        a,b= map(int, sys.stdin.readline().split())
        ins.union(a,b)
    """
    ins.union(0, 1)
    ins.union(2, 3)
    print(ins.find(0, 3))  # False
    ins.union(1, 2)
    print(ins.find(0, 3))  # True
    """
    cnt=[0 for i in range(n+1)]
    for i in range(1,n+1):
        cnt[ins._root(i)]+=1
    print(max(cnt))

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
from itertools import accumulate
import bisect

import sys
input = sys.stdin.readline

def solve(n,m):
    graph = defaultdict(list)
    for _ in range(m):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    connected = []
    unseen = set(range(n))
    while unseen:
        aa = unseen.pop()
        unseen.add(aa)
        stack = [aa]
        cnt = 0
        while stack:
            bb = stack.pop()
            if bb in unseen:
                stack.extend(graph[bb])
                unseen.remove(bb)
                cnt += 1
        connected.append(cnt)
    #print(connected)
    print(max(connected))
            


            

def main():
    n,m = map(int,input().split())
    solve(n,m)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())

color = []
colorStorage = []
for i in range(N):
    color.append(i)
    colorStorage.append([i])

for _ in range(M):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    if color[p] == color[q]:
        continue
    else:
        x = color[p]
        y = color[q]
        if len(colorStorage[x]) >= len(colorStorage[y]):
            for elem in colorStorage[y]:
                color[elem] = x
                colorStorage[x].append(elem)
            colorStorage[y] = []
        else:
            for elem in colorStorage[x]:
                color[elem] = y
                colorStorage[y].append(elem)
            colorStorage[x] = []
maxL = 0
for colorList in colorStorage:
    if maxL < len(colorList):
        maxL = len(colorList)
print(maxL)

Submission status: Accepted

Solution code:
class union_find:
    def __init__(self, N):
        # 子なら親のインデックス、親ならunionのサイズを負数で格納
        self.par = [-1 for i in range(N)]
    
    def root(self, i):
        if self.par[i] < 0:
            return i
        else:
            # 経路圧縮
            self.par[i] = self.root(self.par[i])
            return self.par[i]
    
    def same(self, a, b):
        return self.root(a) == self.root(b)
    
    def unite(self, a, b):
        if not self.same(a, b):
            self.par[self.root(a)] += self.par[self.root(b)]
            self.par[self.root(b)] = self.root(a)

N, M = list(map(int, input().split()))
UF = union_find(N)
for _ in range(M):
    A, B = list(map(lambda x: int(x) - 1, input().split()))
    UF.unite(A, B)
    # print(UF.par)
print(-min(UF.par))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)] # parents
        self.rank = [1] * n # height of tree
        self.size = [1] * n # size[i] -> iをrootとするgroupのサイズ

    # 木の根を返す
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # xとyの属する集合を併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
            self.size[y] += self.size[x] 
        else:
            self.parents[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # xとyが同じグループに属しているかを判定する
    def same(self, x, y):
        return self.find(x) == self.find(y)

    #--- option ---#

    # xが属する集合の大きさを返す
    def group_size(self, x):
        return self.size[self.find(x)]

    # xが属する集合の要素を返す
    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()}


uf = UnionFind(n)

# unionによるグループの併合
for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a - 1, b - 1)

print(max([uf.group_size(x) for x in uf.parents]))

Submission status: Accepted

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 members(self, x):
    #    root = self.find(x)
    #    return [i for i in range(self.n) if self.find(i) == root]
    def unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def roots(self):
        #全ての根の要素のリスト
        return [i for i, x in enumerate(self.parents) if x<0]
    def group_count(self):
        #グループの数
        return len(self.roots())
    def members(self, x):
        root = self.find(x)
        return len([i for i in range(self.n) if self.find(i) == root])
    #def __str__(self):
    #   return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=reads()
uf=UnionFind(n)
a,b=[0 for i in range(m)],[0 for i in range(m)]
for i in range(m):
    a,b=reads()
    uf.unite(a-1,b-1)
ls=uf.roots()
dic=defaultdict(int)
max=0
y=0
for i in range(n):
    dic[uf.find(i)]+=1
#print(dic)
for num in dic.values():
    if num>max:
        max=num
print(max)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
import sys
sys.setrecursionlimit(10**9)
rks = [None] *n
p = [set([]) for i in range(n)]
flist = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    flist[a-1].append(b-1)
    flist[b-1].append(a-1)
def dfs(graph,w,c):
    if rks[w] is None:
        rks[w] = 0
    for i in range(len(graph[w])):
        if rks[graph[w][i]] is not None:
            continue
        p[c].add(flist[w][i])
        dfs(graph, graph[w][i],c)
c = -1
for w in range(n):
    c += 1
    if rks[w] is None:
        dfs(flist,w,c)
ans = 0
for i in range(n):
    ans = max(ans,len(p[i])+1)
print(ans)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
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 = readInts()
# G = [[] for _ in range(n)]
# for i in range(m):
#     a,b = readInts()
#     a-=1;b-=1;
#     G[a].append(b)
#     G[b].append(a)
uni = UnionFind(n)
for i in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    uni.union(a,b)
ans = -1
for i in range(n):
    a = uni.size(i)
    ans = max(ans,a)
print(ans)

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    n,m = map(int, input().split())
    tomo=[[] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        tomo[a-1].append(b-1)
        tomo[b-1].append(a-1)
    visited=[0 for i in range(n)]
    stack=[]
    group=0
    temp=0
    for i in range(n):
        visited[i]=1
        temp=1
        for j in tomo[i]:
            if visited[j]==0:
                stack.append(j)
                visited[j]=1
                temp+=1
        while len(stack)>=1:
            v = stack.pop(-1)
            for j in tomo[v]:
                if visited[j]==0:
                    stack.append(j)
                    visited[j]=1
                    temp+=1
        group=max(group,temp)
    print(group)






if __name__ == "__main__":

    main()

Submission status: Accepted

Solution code:
def main():
    N,M=map(int,input().split())

    G=[[] for i in range(N)]

    for i in range(M):
        a,b=map(int,input().split())
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)

    trace=[-1 for i in range(N)]
    GroupN=[]

    for i in range(N):
        stack=[]
        if trace[i]==-1:
            trace[i]=0
            stack.append(i)
        Group_tmp=[]
        while len(stack)>0:
            index=stack.pop()
            Group_tmp.append(index)
            for j in G[index]:
                if trace[j]==-1:
                    trace[j]=0
                    stack.append(j)
        if len(Group_tmp)!=0:
            GroupN.append(len(Group_tmp))

    print(max(GroupN))


if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
F = [set() for _ in range(N)]
for _ in range(M):
  a,b = map(lambda x: int(x)-1, input().split())
  F[a].add(b)
  F[b].add(a)

from collections import deque
 
def bfs():
  ans = 1
  done = set()
  for i in range(N):
    if i in done: continue
    queue = deque([i])
    num = 0
    while queue:
      p = queue.popleft()
      for p2 in F[p]:
        if p2 in done: continue
        done.add(p2)
        queue.append(p2)
        num += 1
    ans = max(ans,num)
  return ans
print(bfs())

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(N)

for i in range(M):
    A,B=map(int,input().split())
    uf.union(A-1,B-1)

print(max([uf.size(i) for i in range(N)]))

Submission status: Accepted

Solution code:
from sys import stdin,stdout
from collections import defaultdict
import math
from bisect import bisect
input=stdin.readline
#def print(x):stdout.write(str(x)+'\n')
n,m=map(int,input().split())
l=[0]*n
d=defaultdict(set)
for i in range(m):
    v1,v2=map(int,input().split())
    d[v1-1].add(v2-1)
    d[v2-1].add(v1-1)
for i in d:
    d[i]=list(d[i])
ans=[]
for i in range(n):
    s=[]
    c=0
    if not l[i]:
        s.append(i)
        l[i]=1
        c=1
        for j in s:
            for k in d[j]:
                if not l[k]:
                    s.append(k)
                    l[k]=1
                    c+=1
        ans.append(c)
#print(ans)
print(max(ans))

Submission status: Accepted

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

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.parents[x] > self.parents[y]:
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx

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

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

    def group_size(self):
        return {i: -v for i, v in enumerate(self.parents) if v < 0}

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    uf.unite(a, b)
print(max(uf.group_size().values()))

Submission status: Accepted

Solution code:

# Python3 program to implement Disjoint Set Data 
# Structure. 
  
class DisjSet: 
    def __init__(self, n): 
        # Constructor to create and 
        # initialize sets of n items 
        self.rank = [1] * n 
        self.parent = [i for i in range(n)] 
  
  
    # Finds set of given item x 
    def find(self, x): 
          
        # Finds the representative of the set 
        # that x is an element of 
        if (self.parent[x] != x): 
              
            # if x is not the parent of itself 
            # Then x is not the representative of 
            # its set, 
            self.parent[x] = self.find(self.parent[x]) 
              
            # so we recursively call Find on its parent 
            # and move i's node directly under the 
            # representative of this set 
  
        return self.parent[x] 
  
  
    # Do union of two sets represented 
    # by x and y. 
    def Union(self, x, y): 
          
        # Find current sets of x and y 
        xset = self.find(x) 
        yset = self.find(y) 
  
        # If they are already in same set 
        if xset == yset: 
            return
  
        # Put smaller ranked item under 
        # bigger ranked item if ranks are 
        # different 
        if self.rank[xset] < self.rank[yset]: 
            self.parent[xset] = yset 
  
        elif self.rank[xset] > self.rank[yset]: 
            self.parent[yset] = xset 
  
        # If ranks are same, then move y under 
        # x (doesn't matter which one goes where) 
        # and increment rank of x's tree 
        else: 
            self.parent[yset] = xset 
            self.rank[xset] = self.rank[xset] + 1
  
# Driver code 
'''obj = DisjSet(5) 
obj.Union(0, 2) 
obj.Union(4, 2) 
obj.Union(3, 1) 
if obj.find(4) == obj.find(0): 
    print('Yes') '''
n,m=map(int,input().split())
obj = DisjSet(n)
for i in range(m):
    a,b=map(int,input().split())
    obj.Union(a-1,b-1) 
c=0
l1=[0]*n
for i in range(n):
    l1[obj.find(i)]+=1
print(max(l1))

Submission status: Accepted

Solution code:
from collections import Counter

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

par = [i for i in range(n + 1)]
rank = [0 for _ in range(n + 1)]

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

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

def unite(x, y):
    x = root(x)
    y = root(y)

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

for a, b in edges:
    unite(a, b)

roots = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    roots[i] = root(i)

roots_cnt = Counter(roots)
print(max(roots_cnt.values()))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ad_list = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in ad_list:
    ad_list[a].add(b)
  else:
    ad_list[a] = {b}
  if b in ad_list:
    ad_list[b].add(a)
  else:
    ad_list[b] = {a}

#BFS
ans = 0
done = [True for i in range(N+1)]

import queue
q = queue.Queue()

for i in range(1, N+1):
  if done[i]:
    done[i] = False
    tmp = 1
    if i in ad_list:
      q.put(i)
      while not q.empty():
        x = q.get()
        for y in ad_list[x]:
          if done[y]:
            tmp += 1
            done[y] = False
            q.put(y)
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

n,m=map(int,input().split())
friend=dict()
# 関係をdictにとる
for i in range(m):
  a,b=map(int,input().split())
  if a-1 in friend:
    friend[a-1].append(b-1)
  else:
    friend[a-1] = [b-1]
  if b-1 in friend:
    friend[b-1].append(a-1)
  else:
    friend[b-1] = [a-1]
# 次に、数珠つなぎでdfs
memo = [0]*n

def dfs(who,v):
  if memo[who]:
    return 0
  memo[who] = v
  res = 1
  if who not in friend:
    return 1
  for x in friend[who]:
    res += dfs(x, v)
  return res

ans = 0
c = 1
for i in range(n):
  if not memo[i]:
    ans = max(ans, dfs(i,c))
    c += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        #親の添字、親自身は木の要素数*-1をもつ
        self.root = [-1]*(n)
        #枝の最大長さ
        self.rank = [0]*(n)
        #最大メンバー数
        self.maxmem = 1

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
    #高さによる合併    
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return 
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.maxmem < -1*self.root[x]:
                self.maxmem = -1*self.root[x]
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1
            if self.maxmem < -1*self.root[y]:
                self.maxmem = -1*self.root[y]
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]    
    
    def members(self, x):
        root = self.find_root(x)
        return [i for i in range(self.n) if self.find_root(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.root) 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()}
    
n, m = map(int,input().rstrip().split())
ab = [list(map(int,input().split()))for _ in range(m)]

u = UnionFind(n)
for a,b in ab:
    u.unite(a-1,b-1)
print(u.maxmem)

Submission status: Accepted

Solution code:
n, m  = map(int,  input().split())
vertices = range(1,n+1)
adj =  {v: set() for  v  in vertices}
for _  in range(m):
    s, t  = map(int,  input().split())
    adj[s].add(t)
    adj[t].add(s)

ans = 0
reached = {v: False for v in vertices}
for v in vertices:
    if not reached[v]:
        i = 1
        reached[v] = True
        stack = [v]
        while stack:
            w = stack.pop()
            for u in  adj[w]:
                if not reached[u]:
                    reached[u] = True
                    stack.append(u)
                    i += 1
        ans = max(ans, i)
print(ans)