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 collections import Counter as cc
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())
class UnionFind():
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.height = [0]*n

    def get_root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.get_root(self.parent[i])
            return self.parent[i]
        
    def unite(self, i, j):
        root_i = self.get_root(i)
        root_j = self.get_root(j)
        if root_i != root_j:
            if self.height[root_i] < self.height[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i
                if self.height[root_i] == self.height[root_j]:
                    self.height[root_i] += 1
    
    def is_in_group(self, i, j):
        if self.get_root(i) == self.get_root(j):
            return True
        else:
            return False

def main():
    n, m = mi()
    uf = UnionFind(n)
    for i in range(m):
        a, b = mi()
        a -= 1
        b -= 1
        uf.unite(a, b)
    for i in range(n):
        uf.get_root(i)
    c = cc(uf.parent)
    ans = max(c.values())
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
arr = list([] for i in range(N+1))
for i in range(M):
    A,B = map(int, input().split())
    arr[A].append(B)
    arr[B].append(A)

from collections import deque
q = deque()
vis = [0 for i in range(N+1)]

def BFS(t):
    count = 1
    q.append(t)
    while q:
        x = q.popleft()
        for i in arr[x]:
            if vis[i] == 0:
                vis[i] = 1
                count += 1
                q.append(i)
    return count

ans = 0
for i in range(1,N+1):
    if vis[i] == 0:
        vis[i] = 1
        ans = max(BFS(i),ans)

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

print(nux)

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)
ans = 0
for i in range(N):
    ans = max(ans,uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())    
       
AB = [None]*M
for i in range(M):
    a,b = map(int,input().split())
    if a>b:
        a,b=b,a
    AB[i] = (a-1,b-1)

AB=set(AB)

tree=[[] for _ in range(N)]
for a,b in AB:
    tree[a].append(b)
    tree[b].append(a) #aがbの親、とかが保証されてれば不要。

from collections import deque

groups=[]
been=[0]*N
for i in range(N):
    if been[i]==0:
        group=[i]
        been[i]=1
        q = deque([(i,togo) for togo in tree[i]]) 
        while q:
            parent,x = q.popleft()
            if been[x]==1:
                continue
            been[x]=1
            group.append(x)
            for y in tree[x]:
                if y == parent:#親ノードを飛ばし
                    continue
                q.append((x,y))#子ノードを追加
        groups.append(group)

print(max( len(g) for g in groups))

Submission status: Accepted

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

class UF:
    def __init__(self, num):
        self.parent = [i for i in range(num + 1)]
        self.rank = [1] * (num + 1)

    def unite(self, x, y):
        xpar = self.find(x)
        ypar = self.find(y)
        if xpar == ypar:
            return
        if self.rank[xpar] == self.rank[ypar]:
            self.parent[ypar] = self.parent[xpar]
            self.rank[xpar] += 1
        elif self.rank[xpar] > self.rank[ypar]:
            self.parent[ypar] = self.parent[xpar]
        else:
            self.parent[xpar] = self.parent[ypar]

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

groups = UF(N)

for i in range(M):
    a, b = map(int, input().split())
    groups.unite(a, b)

counts = {i:0 for i in range(N+1)}

for i in range(N+1):
    counts[groups.find(i)] += 1

print(max(counts.values()))

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

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

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

    def size(x):
        return -par[find(x)]

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

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

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

    n, m = map(int, input().split())
    par = [-1] * n
    m = map(int, read().split())
    ab = zip(m, m)
    abs = set()
    for a, b in ab:
        a -= 1
        b -= 1
        tmp = (min(a, b), max(a, b))
        abs.add(tmp)
    for abse in abs:
        unite(abse[0], abse[1])
    rs = roots()
    r = 0
    for rse in rs:
        r = max(r, size(rse))
    print(r)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

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

    # ノードxのrootノードを見つける
    def findRoot(self, x):
        if(self.root[x] < 0): # 根
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.findRoot(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.findRoot(x)
        y = self.findRoot(y)
        # すでに同じ木に属していた場合
        if x == y:
            return 
        # 違う木に属していた場合rankを見てくっつける方を決める
        if self.rank[x] > self.rank[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.rank[x] == self.rank[y]:
                self.rank[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

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

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

    uf = UnionFind(n)

    for _ in range(m):
        a, b = i_map()
        
        if uf.isSameGroup(a, b):
            continue
        else:
            uf.unite(a, b)

    max_count = 0
    for i in range(n):
        max_count = max(max_count, uf.count(i))

    print(max_count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


G = unionFind(N)

for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)

C = collections.Counter(G.parent).most_common()

print(C[0][1])

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())

    par = [i for i in range(N)]
    size = [1 for i in range(N)]

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

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

    def union(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return
        if size[x] < size[y]:
            x, y = y, x
        size[x] += size[y]
        par[y] = x

    def get_size(x):
        return size[find(x)]

    for _ in range(M):
        a, b = (int(i)-1 for i in input().split())
        union(a, b)

    ans = max(get_size(i) for i in range(N))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
n, m = map(int, input().split())

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

uf = UnionFind(n+1)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)

max_mem = 0
for i in range(n+1):
    max_mem = max(max_mem, uf.size(i))
print(max_mem)

Submission status: Accepted

Solution code:
class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

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


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        ##union by rank
        #if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
        #    a_par,b_par = b_par,a_par
        #if self.rnks[a_par] == self.rnks[b_par]:
        #    self.rnks[a_par] += 1
        if self.size(a_par) < self.size(b_par): #parentsの値が負の数のとき、それはその木のサイズを表す。
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)

def main():
    n,m = map(int,input().split())
    uf = UF(n)
    for i in range(m):
        a,b = map(int,input().split())
        uf.union(a,b)
    mx = -1
    for i in range(n):
        mx = max(uf.size(i),mx)
    print(mx)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
# your code goes here
from heapq import heappop ,heappush
def bfs(k):
    
    q=[k]
    vis[k]=1
    #p.append(k+1)
    while len(q):
        
        
        curr=heappop(q)
        p.append(curr+1)
        #print(vis, v[curr+1])
        for c in v[curr+1]:
            #print(c)
            if vis[c-1]==0:
                a.append(c)
                
                heappush(q,c-1)
                vis[c-1]=1
            
    
n,m=map(int,input().split())
v=defaultdict(list)
vis=[0]*n
p=[]

for i in range(m):
    a,b=map(int,input().split())
    v[a].append(b)
    v[b].append(a)
ans=0      
for i in range(n):
    if vis[i]==0:
        a=[i+1]
        bfs(i)
        ans=max(ans,len(a))
        #print(a)
    

print(ans)

Submission status: Accepted

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

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

uf=UnionFind(N)
for i in range(M):
    uf.union(x[i][0]-1,x[i][1]-1)

ans=0
for i in uf.parents:
    gsize=uf.size(i)
    ans=max(gsize,ans)

print(ans)

Submission status: Accepted

Solution code:
def find_par(x,p):
    
    try :
        if x == p[x] :
            return x

        p[x] = find_par(p[x],p)
        return p[x]
    except:
        return x


def union(x,y,p,size):
    try:
        xp = find_par(x,p)
        yp= find_par(y,p)

        if xp != yp:
            p[yp] = xp
            size[xp] += size[yp]
    except:
        pass
    
n,m=[int(c) for c in input().split()]
p=[i for i in range(n+1)]
size =[1 for i in range(n+1)]
for i in range(m):
    a,b =[int(c) for c in input().split()]
    union(a,b,p,size)

roots= set()

for i in range(1,n+1):
    par = find_par(i,p)
    roots.add(par)

ans = float("-inf")
for pp in roots:
    try:
        ans = max(ans,size[pp])
    except:
        pass

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)]


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

ans = 0
for i in range(N):
    ans = max(Groups.size(i), ans)

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

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


sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N, M = map(int, input().split())
AB =  [list(map(int, input().split())) for _ in range(M)]
ans = 0
uf = UnionFind(N)

for i in range(M):
    uf.union(AB[i][0]-1, AB[i][1]-1)

for i in range(N):
    ans = max(ans,uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
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 unite(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 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())
    U = UnionFind(n)
    for _ in range(m):
        a,b = map(int,input().split())
        U.unite(a-1,b-1)
    
    d = Counter()
    for i in range(n):
        d[U.find(i)]+=1
    
    print(max(d.values()))
main()

Submission status: Accepted

Solution code:
#abc177 d
import sys,math,collections,itertools
input = sys.stdin.readline

N,M=list(map(int,input().split()))
frend=[[] for _ in range(N+1)]
for _ in range(M):
    A,B=list(map(int,input().split()))
    frend[A].append(B)
    frend[B].append(A)

#仲間グループを作る
group=[0]*(N+1)
q = collections.deque([])
no_seen = set(range(1,N+1))
No=0
while no_seen:
    q.append(no_seen.pop())
    No += 1
    while q:
        now = q.popleft()
        group[now]=No
        for member in frend[now]:
            if member in no_seen:
                q.append(member)
                no_seen.discard(member)

gc=collections.Counter(group)
print(gc.most_common()[0][1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
friends = [set() for _ in range(N)]
for __ in range(M):
    a, b = map(int, input().split())
    if b-1 not in friends[a-1]:
        friends[a-1] |= {b-1}
    if a-1 not in friends[b-1]:
        friends[b-1] |= {a-1}
check = [0 for _ in range(N)]
ans = 0
for i in range(N):
    if check[i]:
        continue
    count = 1
    next = [i]
    check[i] = 1
    while next:
        fri = next.pop()
        for F in friends[fri]:
            if check[F]:
                continue
            count += 1
            check[F] = 1
            next.append(F)
    ans = max(ans, count)
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 i in range(M):
  a,b = map(int, input().split())
  uf.union(a-1,b-1)
res=-1
for i in range(N):
  res = max(res,uf.size(i))
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

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 solve():
    N, M = MI()

    uf = UnionFind(N)
    for i in range(M):
        a, b = MI1()
        uf.union(a, b)
    
    tmp = []
    # print(uf.roots())
    for r in uf.roots():
        # print(uf.size(r))
        tmp.append(uf.size(r))
    s = sorted(tmp, reverse=True)
    # print(s)
    if len(s) == 1:
        print(s[0])
    else:
        print(s[1] + s[0] - s[1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin
N,M = map(int,input().split())
F = [list(map(int,stdin.readline().split())) for i in [0]*M]
G = [[] for i in [0]*(N+1)]
for i in F:
    G[i[0]].append(i[1])
    G[i[1]].append(i[0])

def main(n,m,g):
    visited = [False for i in [0]*(n+1)]
    ans = 1
    for i in range(n+1):
        if visited[i]:
            continue
        q = [i]
        temp = 1
        while q:
            #print(q)
            #print(temp)
            node = q.pop(0)
            visited[node] = True
            adj = g[node]
            for j in adj:
                if visited[j]:
                    continue
                visited[j] = True
                temp += 1
                q.append(j)
        ans = max(ans,temp)
    print(ans)

if __name__=="__main__":
    main(N,M,G)