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:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def resolve():
    int1 = lambda x: int(x) - 1
    readline=sys.stdin.readline

    n,m=map(int, readline().strip().split())

    uf = UnionFind(n)

    tb=[0]*n

    for i in range(m):
        a,b=map(int1, readline().strip().split())
        uf.Unite(a,b)

    for i in range(n):
        tb[uf.Find_Root(i)]+=1
    print(max(tb))
if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

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]


N,M=list(map(int,input().split()))
uf=UnionFind(N)
for _ in range(M):
    a,b=list(map(int,input().split()))
    a-=1
    b-=1
    uf.union(a,b)

L=set(uf.roots())
ans=0
for k in L:
    ans=max(ans,uf.size(k))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
fiend_memo = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    fiend_memo[a].append(b)
    fiend_memo[b].append(a)
#print(fiend_memo)
make_group = []
ans = 0
d = deque()
d.append(1)
seen = {}
# seen[1] = 1
for person in range(1, n + 1):
    cnt = 0
    if person not in seen.keys():
        d.append(person)
        seen[person] = 1
        cnt += 1
    while d:
        now_person = d.popleft()
        for next_person in fiend_memo[now_person]:
            if next_person not in seen.keys():
                d.append(next_person)
                seen[next_person] = 1
                cnt += 1
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x, y = find(x), find(y)
    if x == y:
        return False
    
    if par[x] > par[y]:
        x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

def same(x,y): #xとyが同じ集合に属するかの判定
    return find(x) == find(y)

def size(x): #xが属する集合の個数
    return -par[find(x)]
n, m = map(int, input().split())
par = [-1]*n

for _ in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
par = [-i for i in par]
print(max(par))

Submission status: Accepted

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

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
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===

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

    e = [[] for _ in range(n)]

    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    visited = [False for _ in range(n)]

    ans = 0
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            cnt = 1
            que = collections.deque()
            que.append(i)

            while que:
                q = que.popleft()

                for ei in e[q]:
                    if not visited[ei]:
                        visited[ei] = True
                        cnt += 1
                        que.append(ei)

            ans = max(ans, cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    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 x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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

n,m=map(int, input().split())
uf1=UnionFind(n)
k=set()
for i in range(m):
    a,b=map(int, input().split())
    a,b=a-1,b-1
    if a>b:
        a,b=b,a
    k.add((a,b))
for a,b in k:
    uf1.union(a,b)

for i in range(n):uf1.find(i)
from collections import *
ans=Counter(uf1.par)

print(ans.most_common()[0][1])

Submission status: Accepted

Solution code:
#region bcf
# code section by Barry Fam
#
# pylint: disable= reimported
#region unionfind.py
# class DisjointSetForest:
class DisjointSetForest(object):  # pylint: disable= useless-object-inheritance
    def __init__(self, iterable=(), **kwarg):
        # super().__init__(**kwarg)
        super(DisjointSetForest, self).__init__(**kwarg)
        self._p = {}
        self._ranks = {}

        for x in iterable: self.make_set(x)

    def make_set(self, x):
        assert x not in self._p
        self._p[x] = x
        self._ranks[x] = 0

    def find(self, x):
        if self._p[x] != x:
            self._p[x] = self.find(self._p[x])
        return self._p[x]

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

        if self._ranks[xr] > self._ranks[yr]:
            self._p[yr] = xr
        else:
            self._p[xr] = yr
            if self._ranks[xr] == self._ranks[yr]:
                self._ranks[yr] += 1

#endregion unionfind.py
#endregion bcf
###############################################################################

import sys
def input(itr=iter(sys.stdin.readlines())):  # pylint: disable= redefined-builtin
    return next(itr).rstrip('\n\r')
###############################################################################

import collections

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

dsf = DisjointSetForest(range(N))
for _ in range(M):
    A, B = map(int, input().split())
    dsf.union(A-1, B-1)

counts = collections.Counter(dsf.find(u) for u in range(N))
print(max(counts.values()))

Submission status: Accepted

Solution code:
# https://note.nkmk.me/python-union-find/
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)
ans = 0
if M == 0:
    print(1)
    exit()
for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1,B-1)
    ans = max(ans,uf.size(A-1))
print(ans)

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 _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
ans = 0    
for i in range(n):
    ans = max(uf.size(i), ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, m = list(map(int, input().split()))

ab = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n+1)]

for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)

visited = [False] * (n+1)

d = 0

for i in range(1, n+1):
    if not visited[i]:
        q = deque([i])
        c = 0
        while len(q) > 0:
            v = q.pop()
            c += 1
            visited[v] = True
            for w in adj[v]:
                if not visited[w]:
                    q.append(w)
                    visited[w] = True
        d = max(d, c)

print(d)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
par=[i for i in range(n)] #親
rank=[1]*n #深さ
size=[1]*n #iを根とするグループのサイズ
#親を見つける
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])
  
#xの属するグループとyの属するグループを併合
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if rank[x]<rank[y]:
    par[x]=y
    size[y]=size[y]+size[x]
  else:
    par[y]=x
    size[x]=size[x]+size[y]
    if rank[x]==rank[y]:
      rank[x]+=1
      
#xとyが同じグループに属するかどうか
def same(x,y):
  return find(x)==find(y)

#check=set()
for i in range(m):
  a,b=map(int,input().split())
  unite(a-1,b-1)
  
ans=0

for i in range(n):
  ans=max(ans,size[find(i)])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
pair = defaultdict(set)
for _ in range(M):
    a, b = map(int, input().split())
    pair[a].add(b)
    pair[b].add(a)

Q = []
visited = set()
max_group = 0
for i in range(N):
    if i not in visited:
        count = 1
        Q.append(i)
        visited.add(i)
        while Q:
            x = Q.pop()
            for friend in pair[x]:
                if friend not in visited:
                    Q.append(friend)
                    visited.add(friend)
                    count += 1
        if max_group < count:
            max_group = count
print(max_group)

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
ab = [[] for i in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
    
chk = [0]*n

cnt = 1

for i in range(n):
    if chk[i] == 0:
        chk[i] = cnt
        q = deque()
        q.append(i)
        while len(q) > 0:
            tmp = q.popleft()
            for j in range(len(ab[tmp])):
                if chk[ab[tmp][j]] == 0:
                    q.append(ab[tmp][j])
                    chk[ab[tmp][j]] = cnt
                    
    cnt += 1

li = [0]*(n+2)

#print(chk)

for i in range(n):
    li[chk[i]] += 1
    
print(max(li))

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 _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    
ans = 0
for i in range(N):
    ans = max(uf.size(i), ans)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


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

    # retrun the root of element x
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # unite the group include element x and group include element y
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # get size of the gourp which element x belongs
    def get_size(self, x):
        return -self.parents[self.find(x)]

    # check if element x and element y is same group
    def same(self, x, y):
        return self.find(x) == self.find(y)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, m = input_int_list()
    union = UnionFind(n + 1)
    for _ in range(m):
        a, b = input_int_list()
        union.unite(a, b)

    ans = min(union.parents) * (-1)
    print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    def find(self, x):
        '''
        要素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が属するグループと要素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):
        '''
        要素xが属するグループのサイズ（要素数）を返す
        '''
        return -self.parents[self.find(x)]

    def same(self, x, y):
        '''
        要素x, yが同じグループに属するかどうかを返す
        '''
        return self.find(x) == self.find(y)

    def members(self, x):
        '''
        要素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())


G = UnionFind(N)

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

ans = 0
for r in G.roots():
    ans = max(ans, G.size(r))
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
from random import randint
##import numpy as np
sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
class Graph: 
      
    # init function to declare class variables 
    def __init__(self,V): 
        self.V = V 
        self.adj = [[] for i in range(V)] 
  
    def DFSUtil(self, temp, v, visited): 
  
        # Mark the current vertex as visited 
        visited[v] = True
  
        # Store the vertex to list 
        temp.append(v) 
  
        # Repeat for all vertices adjacent 
        # to this vertex v 
        for i in self.adj[v]: 
            if visited[i] == False: 
                  
                # Update the list 
                temp = self.DFSUtil(temp, i, visited) 
        return temp 
  
    # method to add an undirected edge 
    def addEdge(self, v, w): 
        self.adj[v].append(w) 
        self.adj[w].append(v) 
  
    # Method to retrieve connected components 
    # in an undirected graph 
    def connectedComponents(self): 
        visited = [] 
        cc = [] 
        for i in range(self.V): 
            visited.append(False) 
        for v in range(self.V): 
            if visited[v] == False: 
                temp = [] 
                cc.append(self.DFSUtil(temp, v, visited)) 
        return cc 
  
# Driver Code 
if __name__=="__main__":
    v,e=cin()
    g = Graph(v+1); 
    for i in range(e):
        a,b=cin()
        g.addEdge(a,b)
        g.addEdge(b,a)
    cc = g.connectedComponents() 
    m=0
    for i in cc:
        m=max(m,len(i))
    print(m)
for _ in range(1):
    a=1
##    n=inin()
##    a=ain()
##    post=pref(a,n,1)+[0]
##    
##    s=0
##    for i in range(n):
##        s=(s+(a[i]*post[i+1])%mo)%mo
##    print(s)
    
    
            
    
    
        
    

        
        
        
    
    
    

        
    

        
        
    
        
    
    
            
    
        
    
    
    

                    
                    
                    
                    
                    
        
    
    
    
    
            
        
    

            
            
            
            
        
        
                
                
    

    
    
    
    
    

                    
                
    

    

        


    
        

    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def dfs(c, to, seen, g = []):
    #print(g)
    if not seen[c]:
        g.append(c)
        seen[c] = 1
    for next in to[c]:
        if not seen[next]:
            dfs(next, to, seen, g)
    return g

def run():
    N, M = map(int, sysread().split())
    to = [[] for i in range(N+1)]
    for _ in range(M):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)
    #print(to)
    groups = {}
    seen = [0] * (N+1)
    max_len = 0
    for i in range(1, N+1):
        #print(i, '---------------------')
        g = dfs(i, to, seen, [])
        if g:
            groups[i] = g
            max_len = max(max_len, len(g))
        #print(i, g)
    print(max_len)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

n,m = map(int, input().split())

f = [[] * (n+1) for i in range(n+1)]

def dfs(i):
  searched[i] = 1
  ans = 1
  for j in f[i]:
    if searched[j] == 0:
      ans += dfs(j)
  return ans

for i in range(m):
  a,b = map(int, input().split())
  f[a].append(b)
  f[b].append(a)

searched=[0]*(n+1)
ans = 0
for i in range(1, n+1):
  # iの友達の数
  if searched[i] == 0:
    ans = max(ans, dfs(i))
print(ans)

Submission status: Accepted

Solution code:
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(set)
    for _ in range(M):
        A, B = map(int, input().split())
        graph[A].add(B)
        graph[B].add(A)

    visited = set()
    min_count = 0
    for i in range(1, N+1):
        if i not in visited:
            cur = set([i])
            visited.add(i)
            cnt = 1
            while cur:
                temp = set()
                for i in cur:
                    for j in graph[i]:
                        if j not in visited:
                            visited.add(j)
                            cnt += 1
                            temp.add(j)
                cur = temp
            min_count = max(min_count, cnt)
    return min_count




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

Submission status: Accepted

Solution code:
import collections
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    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 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
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1

  # 同じ集合に属するか判定
  def same_check(self, x, y):
    return self.find(x) == self.find(y)
n,m = map(int,input().split())
uf = UnionFind(n)
for _ in range(m):
  a,b = map(int,input().split())
  uf.union(a,b)
r = [0 for _ in range(n)]
for i in range(1,n+1):
  r[uf.find(i)-1] += 1
print(max(r))

Submission status: Accepted

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
ilelec = lambda: map(int1,input().split())
alelec = lambda: list(map(int1, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

maxi= 1
first = 1 #if first node is 1
G = defaultdict(list)
def addEdge(a,b):
    G[a].append(b)
    G[b].append(a)

def DFSutil(node,vis):
    global maxi
    stack = deque()
    stack.append(node)
    c=0
    while len(stack) != 0:
        s = stack.pop()
        if not vis[s]:
            vis[s] = True
            c+=1
        for i in G[s]:
            if vis[i] == False:
                stack.append(i)
    maxi = max(maxi,c)
        
    
def countconnectedcompo(first,N):
    vis =[False for i in range(N+first)]
    count = 0
    for i in range(first,N+first):
        #do dfs for all the unvisited node after each dfs
        if vis[i] == False:
            DFSutil(i,vis)
            count+=1
    return count

N,M =ilele()
for i in range(M):
    u,v = ilele()
    addEdge(u,v)
countconnectedcompo(first,N) # N is the total no of nodes
print(maxi)

Submission status: Accepted

Solution code:
ans=0
from collections import Counter,deque
this=list(map(int,input().split()))
n=this[0]
m=this[1]
arr=[]
for _ in range(n+1):
    arr.append([])
for _ in range(m):
    x=list(map(int,input().split()))
    arr[x[0]].append(x[1])
    arr[x[1]].append(x[0])
net=Counter([])
for i in range(1,n+1):
    if net[i]==0:
        visited=Counter([])
        q=deque()
        visited[i]=1
        now=1
        q.append(i)
        while q:
            k=q.popleft()
            for item in arr[k]:
                if visited[item]==0:
                    q.append(item)
                    net[item]=1
                    now+=1
                    visited[item]=1
        ans=max(ans,now)
print (ans)

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, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    uf = UnionFind(N)

    for ab in AB:
        uf.union(ab[0]-1, ab[1]-1)

    ans = 0
    for i in range(N):
        if uf.size(i) > ans:
            ans = uf.size(i)

    print(ans)


if __name__ == "__main__":
    main()