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:
N, M = list(map(int, input().split()))
edges = []
for _i in range(M):
    edges.append(list(map(int, input().split())))

import networkx as nx

G = nx.Graph()
G.add_edges_from(edges)
ans = 1
for comp in nx.connected_components(G):
    # H = G.subgraph(comp)
    # print(H.edges)
    ans = max(ans, len(comp))
print(ans)

Submission status: Accepted

Solution code:
# union find, bfs

import sys
from collections import deque
si = sys.stdin.readline


def main():
    [n, m] = [int(e) for e in si().split()]
    if not m:
        print(1)
        return

    visited = [False]*(n+1)
    fm = [set() for _ in range(n+1)]
    mx, comp = 0, 0

    while m:
        m -= 1
        [a, b] = [int(e) for e in si().split()]
        fm[a].add(b)
        fm[b].add(a)

    for i in range(1, n+1):
        if visited[i]:
            continue
        visited[i] = True
        comp += 1
        q = deque()
        q.append(i)
        cnt = 1
        while q:
            curr = q.popleft()
            for e in fm[curr]:
                if not visited[e]:
                    visited[e] = True
                    q.append(e)
                    cnt += 1
        mx = max(mx, cnt)
    print(mx)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
ans=0


group = [set() for _ in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    group[a].add(b)
    group[b].add(a)


kisyutu = set()
deque = deque()

for i in range(n):
    if i not in kisyutu:
        kisyutu.add(i)
        friend_set=group[i]

        deque.extend(group[i])

        while deque:
            a1 = deque.pop()
            if a1 not in kisyutu:
                kisyutu.add(a1)
                friend_set.add(a1)
                deque.extend(group[a1])
        ans = max(ans, len(friend_set)+1)

if m!=0:
    print(ans)
else:
    print(1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g = [[] for _ in range(n)] # 隣接リスト
from collections import deque
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].append(b)
    g[b-1].append(a)
#print(g)
def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
x=[0]*n
s=1
m=0
for i in range(1,n+1):
    if x[i-1]==0:
        x[i-1]=s
        c=1
        q=deque([i])
        while q:
            v = q.popleft()
            for j in g[v-1]:
                if x[j-1]==0:
                    q.append(j)
                    x[j-1]=s
                    c+=1
        s+=1
        m=max(m,c)
print(m)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict


def main():
    people_count, info_count = [int(x) for x in input().split()]
    if info_count == 0:
        return 1
    if info_count == 1:
        return 2

    friends = [set() for _ in range(people_count)]
    for _ in range(info_count):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    seen = [False] * people_count
    circle_id = 0
    counter = defaultdict(int)
    for i, circle in enumerate(friends):
        if seen[i]:
            continue
        circle_id += 1
        qu = deque()
        qu.append(i)
        seen[i] == 1
        while qu:
            now = qu.popleft()
            for new in friends[now]:
                if seen[new]:
                    continue
                qu.append(new)
                seen[new] = True
                counter[circle_id] += 1
    return max(v for v in counter.values())


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

Submission status: Accepted

Solution code:
import collections # deque, Counter
# import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
# import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# --------------------------------------------------------------

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

road = [[] for i in range(n)] # 頂点vと隣接する頂点のリスト
 
for i in lis:
    i[0]-=1
    i[1]-=1
    road[i[0]].append(i[1])
    road[i[1]].append(i[0])

cmax  = 0
 
uf = UnionFind(n)

for i in lis:
    uf.union(i[0],i[1])

for i in range(n):
    cmax = max(cmax, uf.size(i))

print(cmax)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
from collections import deque
e = [list() for _ in range(n)]
for i in range(m):
    e[ab[i][0]-1] += [ab[i][1]-1]
    e[ab[i][1]-1] += [ab[i][0]-1]

stack = deque()
visited = [0]*n

def dfs(x):
    num = 0
    stack.append(x)
    while stack:
        v = stack.pop()
        for k in e[v]:
            if visited[k]==0:
                num +=1
                visited[k]=1
                stack.append(k)
    return num


li = []

for i in range(n):
    li += [dfs(i)]

ans = max(li)
if ans ==0:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque


def main():
    N, M = map(int, input().split())
    A = [0] * M
    B = [0] * M

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

    friends = defaultdict(set)

    for i in range(M):
        a, b = A[i], B[i]
        friends[a].add(b)
        friends[b].add(a)

    seen = [False] * N

    # print(friends)

    def dfs(start):
        cnt = 0
        nodes = []

        todo = deque([start])
        while len(todo) > 0:
            v = todo.pop()
            cnt += 1
            nodes.append(v)

            for next_v in friends[v]:
                if seen[next_v]:
                    continue
                else:
                    todo.append(next_v)
                    seen[next_v] = True

        return cnt, nodes

    trees = []
    counts = []
    for v in range(N):
        if seen[v]:
            continue
        else:
            seen[v] = True
            c, nodes = dfs(v)
            counts.append(c)
            trees.append(nodes)

    # print(counts)
    # print(trees)
    print(max(counts))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)
    explored = set()

    sstock = collections.deque([i for i in range(1,n+1)])
    ans = 0
    while len(sstock)!=0:
        nnext = sstock.pop()
        if nnext not in explored:
            cnt = 0
            stock = collections.deque([nnext])
            explored.add(nnext)
            while len(stock) != 0:
                next = stock.pop()
                cnt += 1   
                for i in route[next]:
                    if i not in explored:
                        stock.append(i)
                        explored.add(i)
            ans = max(ans,cnt)
    print(ans)
main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [0] * n
        self.chi = [0] * n
        for i in range(n):
            self.par[i] = i
            self.chi[i] = 1
        self.max_child = 1
    def root(self, x):
        if self.par[x] == x:
            return x
        rx = self.root(self.par[x])
        self.par[x] = rx
        #if self.chi[x] < self.chi[rx]:
        #    self.chi[x] = self.chi[rx]
        return self.par[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        #print("rx = ", rx, "ry = ", ry)
        #print("self.chi[rx] = ", self.chi[rx])
        #print("self.chi[ry] = ", self.chi[ry])
        self.par[rx] = ry
        self.chi[ry] += self.chi[rx]
        if self.max_child < self.chi[ry]:
            self.max_child = self.chi[ry]
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

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

u = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    u.unite(a-1, b-1)
    #print("self.par[", a-1, "] = ", u.par[a-1])
    #print("self.par[", b-1, "] = ", u.par[b-1])
    #print("self.chi[", a-1, "] = ", u.chi[a-1])
    #print("self.chi[", b-1, "] = ", u.chi[b-1])
    

print(u.max_child)
#for i in range(n):
#    print(u.par[i])

Submission status: Accepted

Solution code:
from collections import Counter

# UnionFind
# 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 max_children(self):
        return max([self.size(x) for x in range(self.n)])

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# print('input >>')
N, M = map(int,(input().split()))
ABs = []
for _ in range(M):
    ABs.append(tuple(map(lambda x:int(x)-1,(input().split()))))

uf = UnionFind(N)
for AB in ABs:
    A, B = AB
    uf.union(A, B)
    
# print(uf.max_children())
print(uf.max_children())

# print('-----output-----')
# 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)
fr = []
# G = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    fr.append((a,b))
c = []
# tmp_s = set()
for i in range(n):
    c.append(uf.size(i))
    # c[i] = tuple(uf.members(i))
# print(c)
c = set(c)
c = list(c)
c.sort(reverse=1)
if len(c) == 1:
    print(c[0])
else:
    ans = c[1]
    ans += c[0]-c[1]
    print(ans)
# print(c)
# sc = set(c)
# sc = list(sc)
# lenc = []
# for ss in sc:
#     lenc.append(len(ss))
# lenc = set(lenc)
# lenc = list(lenc)
# lenc.sort(reverse=1)
# if len(lenc) == 1:
#     print(lenc[0])
# else:
#     ans = lenc[1]
#     ans += lenc[0]-lenc[1]
#     print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
friend = [set() for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  friend[a-1].add(b-1)
  friend[b-1].add(a-1)

flag = [True for i in range(n)]
max_grupe = 0
for i in range(n):
  if(flag[i] == False):
    continue
  num = 0
  queue = deque([i])
  flag[i] = False
  while queue:
    now = queue.popleft()
    num += 1
    for j in friend[now]:
      if(flag[j]):
        queue.append(j)
        flag[j] = False
        
  max_grupe = max(max_grupe, num)
  
print(max_grupe)

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


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

mx = 0
for i in range(1, N+1):
    mx = max(mx, u.size(i))

print(mx)

Submission status: Accepted

Solution code:
# Union Find

# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


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


# xが属する集合の個数
def size(x):
    return -par[find(x)]


# 初期化
# 根なら-size,子なら親の頂点


N, M = map(int, input().split())
par = [-1] * N
for i in range(M):
    A, B = map(int, input().split())
    unite(A - 1, B - 1)

max_num = 0
for i in range(N):
    max_num = max(max_num, size(i))
print(max_num)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
import collections

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

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

for j in range(n):
    if dist[j]==-1:
        dist[j]=ans
        d=deque([j])
    
        while d:
            v=d.popleft()
            for i in friends[v]:
                if dist[i]!=-1:
                    continue
                dist[i]=ans
                d.append(i)
        ans+=1   
c = collections.Counter(dist)
print(c.most_common()[0][1])

Submission status: Accepted

Solution code:
import collections
n,m=map(int,input().split())
par=[i for i in range(n+1)]
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
for _ in range(m):
    a,b=map(int,input().split())
    A=find(a)
    B=find(b)
    par[max(A,B)]=par[min(A,B)]
l=[]
for i in range(1,n+1):
    l.append(find(i))
l=collections.Counter(l)
print(max(l.values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

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

    seen = [False] * N
    friends_group = []
    for i in range(N):
        if seen[i]:
            continue
        q = deque([i])
        tmp_group = set([i])
        while q:
            now = q.popleft()
            if seen[now]:
                continue
            seen[now] = True
            for j in friends_input[now]:
                if not seen[j]:
                    q.append(j)
                    tmp_group.add(j)
        friends_group.append(tmp_group)
    ans = 0
    for i in friends_group:
        ans = max(ans, len(i))
    print(ans)


if __name__ == '__main__':
    main()

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

print(main())

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

class UnionFind():
    def __init__(self, n):
        # uf.parentsで各ノードの親をリストで返す
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        # uf.find(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):
        # uf.union(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):
        # uf.size(x)で処理を行う
        # 要素xが属するグループの要素数を返す
        return -self.parents[self.find(x)]

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

    def members(self, x):
        # uf.members(x)で処理を行う
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # uf.roots()で処理を行う
        #　すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        # uf.group_count()で処理を行う
        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):
        # all_group_members()で処理を行う
        # ｛ルート要素：[グループに属する要素のリスト]｝をdict型で返す
        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 = mp()
uf = UnionFind(n)
used = set()
for i in range(m):
    a,b = mp()
    if (a,b) not in used:
        uf.union(a-1,b-1)
        used.add((a,b))
        used.add((b,a))
ans = -1
for i in range(n):
    ans = max(uf.size(i), ans)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
from collections import deque
friends = [deque() for _ in range(N)]
ans = 0

for a,b in AB:
  a -= 1
  b -= 1
  friends[a].append(b)
  friends[b].append(a)
  
flag = [False] * N
for i in range(N):
  if flag[i]:
    continue
  else:
    x = friends[i]
    tmp = 1
    flag[i] = True
    while len(x)!=0:
      y = x.pop()
      if flag[y]:
        continue
      else:
        tmp += 1
        for j in friends[y]:
          x.append(j)
        flag[y] = True
    ans = max(tmp,ans)
    
print(ans)

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)
for i in range(m):
    a,b=map(int, input().split())
    uf1.union(a-1,b-1)

for i in range(n):uf1.find(i)
X = uf1.par

ans = [0]*n
for i in range(n):
    ans[X[i]] += 1
    
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
Node = [[] for _ in range(N + 1)]

for i in range(M):
    a, b = map(int, input().split())
    Node[a].append(b)
    Node[b].append(a)
#print(Node)

seek = [False]*(N+1)
que = deque()
R = []


for n in range(1, N + 1):
    if seek[n] == True:
        #print('already found: {}'.format(n))
        continue
    result = []
    que.append(n)
    result.append(n)
    seek[n] = True
    while len(que) > 0:
        start = que.pop()
        for node in Node[start]:
            if seek[node] == False:
                result.append(node)
                que.append(node)
                seek[node] = True
    R.append(result)

Max = 0
for l in R:
    if len(l) > Max:
        Max = len(l)
print(Max)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi

Union-Find木の実装は下記サイトを参考にした。
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 main():
    N, M = map(int, input().split())
    Edge_lsit = []
    for i in range(M):
        A, B = map(int, input().split())
        Edge_lsit.append((min(A, B), max(A, B)))
    Edge_lsit.sort()

    uf = UnionFind(N)
    for Edge in Edge_lsit:
        uf.union(Edge[0]-1, Edge[1]-1)
    
    max_size = 0
    for i in range(N):
        max_size = max(max_size, uf.size(i))
    print(max_size)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_root(y)
    if rx == ry:
      return
    if self.rank[rx] < self.rank[ry]:
      self.parent[rx] = ry
    else:
      self.parent[ry] = rx
      if self.rank[rx] == self.rank[ry]:
        self.rank[rx] += 1
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

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)

for i in range(N):
  uf.find_root(i)
c = collections.Counter(uf.parent)
print(c.most_common()[0][1])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

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

    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)

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


N, M = map(int, input().split())
A, B = [0] * M, [0] * M  # 入力時に 0-index に合わせる

direct =[[] for _ in range(N)]  # 同じ集合の友達もしくはブロック関係の人
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    direct[A[i]].append(B[i])
    direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

ans = [0] * N
for i in range(N):
    ans[i] = uf.group_size(i)
print(max(ans))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[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+1)
for i in range(m):
  if uf.same(ab[i][0], ab[i][1]) == False:
    uf.union(ab[i][0], ab[i][1])
ans=0
for i in range(1,n+1):
  if ans <uf.size(i):
    ans=uf.size(i)
print(ans)