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:
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:
from networkx import*
_, *t = map(str.split, open(0))
print(max(1, 1, *map(len,connected_components(Graph(t)))))

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    ab=[map(lambda x: int(x)-1,input().split()) for _ in range(m)]
    uf=UnionFind(n)
    for a,b in ab:
        uf.union(a,b)
    ans = 0
    for s in uf.roots():
        ans = max(uf.size(s),ans)
    print(ans)

class UnionFind():
    '''Union-Find'''
    
    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 is_same(self, x, y) -> bool:
        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())
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# osa9さんの解答を写経 → parの数値周りをわかりやすいように変更
# 解法：最も人数の多い友達集合の要素数分のグループに分ければ良い
# (1,3),(1,5),(2,4)は(1,3,5),(2,4)と等しい(友達の友達は友達)
# なので1,3,5の3人を別々のグループにするために最低3つのグループが必要という解になる

# Counterはリストの要素の出現個数をカウントするメソッド
from collections import Counter

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

# 人数情報と任意の一人を引数にその一人の友達が誰かを辿る関数
def parent(par, i):
    depth = 1
    while par[i-1]!=i:  # 
        i = par[i-1]
        depth += 1
    return i, depth

# 人数の情報(par)と友達関係の情報を引数にparを友達集合に変換する
def union(par, a, b):
    pa, da = parent(par, a)
    pb, db = parent(par, b)
    if da < db:
        par[pa-1] = par[pb-1]
    else:
        par[pb-1] = par[pa-1]

# par_org=[0,1,2,3,4]
par = [i for i in range(1,n+1)]

# Tips：for文カウンタをfor文無いで使用しない時はアンダーバーを使用
for _ in range(m):
    a,b = map(int,input().split())
    union(par, a, b)

c = Counter()
for i in range(n):
    c.update([parent(par,i)[0]])

# 出現回数順に要素を取得するmost_commonメソッド
# most_commonの引数には返り値の要素数(デフォは全部)
# 返り値はタプル型で("要素","出現回数")の形で返ってくるため、most_common(1)[0]で最頻出のタプル
# 後ろの[1]で返り値タプルの"出現回数"の値を表示させている
print(c.most_common(1)[0][1])

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
roots = uf.roots()
cnt = []
for r in roots:
    cnt.append(uf.size(r))
cnt.sort(reverse=True)
ans = cnt[0]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

def parent(par, i):
    depth = 0
    while par[i] != i:
        i = par[i]
        depth +=1
    return i, depth

def union(par, a, b):
    pa, da = parent(par, a)
    pb, db = parent(par, b)
    if da < db:
        par[pa] = par[pb]
    else:
        par[pb] = par[pa]

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

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

c = Counter()
for i in range(N):
    c.update([parent(par, i)[0]])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque

n, m = map(int, input().split())
l = [[] for i in range(n)]
union = []
vis = [-1]*n
ans = 0

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

q = deque()

def dfs(a):
    if vis[a] == -1:
        vis[a] = 0
        temp.append(a)
        for j in l[a]:
            q.append(j)
    if len(q) > 0:
        b = q.popleft()
        dfs(b)
    return temp

for i in range(n):
    temp = []
    union.append(dfs(i))

for i in union:
    ans = max(ans, len(i))

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        self.size = [1]*n
        self.point = n*(n-1) // 2

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        # size において rx>ry にする
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.point -= self.size[rx]*self.size[ry]
        self.size[rx] += self.size[ry]
        # ryの親をrxに設定 (sizeにおいて "小さい方(ry)を大きい方(rx)に" つなげる)
        self.par[ry] = rx
        return True

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

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

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

uf = UnionFind(N)

for a, b in AB:
    a, b = a-1, b-1
    uf.unite(a, b)

r = max(uf.size)

print(r)

Submission status: Accepted

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

    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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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


N,M = map(int, input().split())
uf = UnionFind(N)
for M in range(M):
  A,B = map(int, input().split())
  uf.union(A,B)

ans = 0
for i in uf.roots():
  ans = max(ans, uf.size(i))
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 (0, M):
	A, B = map(int, input().split())
	uf.union(A-1, B-1)
    
C = []
for i in range (0, N):
	C.append(uf.size(i))

print(max(C))

Submission status: Accepted

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

    def root(self,x):
        stack = []
        tbl = self.table
        while tbl[x]>=0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self,x,y):
        return self.root(x)==self.root(y)
    def union(self,x,y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -=1
        else:
            self.table[r1] = r2
if __name__=='__main__':
    N,M = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(M)]
    uf = UnionFind(N)
    for i in range(M):
        uf.union(AB[i][0]-1,AB[i][1]-1)
    r = [0]*N
    for i in range(N):
        r[uf.root(i)] = r[uf.root(i)] + 1
    print(max(r))

Submission status: Accepted

Solution code:
from collections import deque


N, M = map(int,input().split())
mymap = [ [] for n in range(N) ]
for m in range(M):
    a, b = map(int, input().split())
    mymap[a-1].append(b-1)
    mymap[b-1].append(a-1)
#print(mymap)
myans = 0
check_list = [0 for n in range(N)]

for n in range(N):
    mylist = mymap[n]
    #print(mylist)
    myd = deque()
    for mm in mylist:
        myd.append(mm)
    #print(myd)
    mycnt = 1
    check_list[n] = 1
    while myd:
        tgt = myd.popleft()
        #print(tgt)
        if check_list[tgt] == 0 :
            for e in mymap[tgt]:
                if e > n :
                    myd.append(e)
            mycnt += 1
            check_list[tgt] = 1
    if myans < mycnt:
        myans = mycnt
print(myans)

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.par = [-1] * (n+1)
    self.rank = [0] * (n+1)

  def find(self, x):
    if self.par[x] < 0:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  
  def same_check(self, x, y):
    return self.find(x) == self.find(y)
  
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    
    if x == y:
      return False
    else:
      if self.par[x] > self.par[y]:
        x,y = y,x
        
      self.par[x] += self.par[y]
      self.par[y] = x

      return True

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

#
uni = UnionFind(n)
for i in range(m):
  uni.unite(ab[i][0],ab[i][1])

result = 0
for i in range(n):
  result = max(result, uni.size(i))
print(result)

Submission status: Accepted

Solution code:
from collections import Counter
def solve(n, m, a, b):
    parents = list(range(n+1))
    def root(x):
        if parents[x] != x:
            parents[x] = root(parents[x])
        return parents[x]
    for u, v in zip(a, b):
        u = root(u)
        v = root(v)
        if u > v:
            u, v = v, u
        if u != v:
            parents[v] = u
    return max(Counter(map(root, parents)).values())

n, m = map(int, input().split())
if m > 0:
    a, b = zip(*[map(int, input().split()) for i in range(m)])
else:
    a, b = [], []
print(solve(n, m, a, b))

Submission status: Accepted

Solution code:
from networkx import*
_,*t=map(str.split,open(0))
print(max(1,1,*map(len,eval(dir()[177])(Graph(t)))))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
from collections import defaultdict, deque


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力を取得
    N, M = list(map(int, input().split()))
    G = defaultdict(set)
    for m in range(M):
        A_i, B_i = list(map(int, input().split()))
        G[A_i - 1].add(B_i - 1)
        G[B_i - 1].add(A_i - 1)

    return N, M, G


def main(N: int, M: int, G: dict) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 人数(2 <= N <= 2 * 10**5)
        M (int): 情報の数(0 <= M <= 2 * 10**5)
        G (dict): 情報
    """
    # 求解処理
    seen = [False for i in range(N)]

    ans = 0
    for i in range(N):
        if seen[i]:
            continue
        friends = 0
        que = deque()

        seen[i] = True
        que.append(i)
        friends += 1

        while len(que) > 0:
            v = que.popleft()
            for w in G[v]:
                if not seen[w]:
                    seen[w] = True
                    que.append(w)
                    friends += 1

        ans = max(ans, friends)

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, M, G = get_input()

    # メイン処理
    main(N, M, G)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

class DSU(object):
    
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [1] * n
        self.cycle = False

    def find(self, key):
        if self.parent[key] != key:
            self.parent[key] = self.find(self.parent[key])
        return self.parent[key]

    def union(self, a, b):
        s1, s2 = self.find(a), self.find(b)
        if s1 != s2:
            if self.rank[s1] < self.rank[s2]:
                self.parent[s1] = s2
                self.rank[s2] += self.rank[s1]
            else:
                self.parent[s2] = s1
                self.rank[s1] += self.rank[s2]
        else:
            self.cycle = True
        
    def has_cycle(self):
        return self.cycle
    
    def show_parent(self):
        return self.parent

    def show_rank(self):
        return self.rank

def solve():
    n, m = map(int, input().split())
    d = DSU(n + 1)
    if m > 0:
        for _ in range(m):
            a, b = map(int, input().split())
            d.union(a, b)
        # print(d.show_parent())
        print(max(d.show_rank()))
    else:
        print(1)

solve()

Submission status: Accepted

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

#n = int(input())
#l = list(map(int, input().split()))

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


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


aaa=UnionFind(n)

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

#print(a)
#print(aaa)
ans=0
for i in range(n):
    if ans<aaa.size(i):
        ans=aaa.size(i)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n, m = rli()
	seen = defaultdict(lambda: False)
	G = [[] for _ in range(n)]
	for _ in range(m):
		u, v = rli()
		u -= 1
		v -= 1
		u, v = min(u, v), max(u, v)
		if seen[(u, v)]: continue
		seen[(u, v)] = True
		G[u].append(v)
		G[v].append(u)
	sizes = []
	seen2 = defaultdict(lambda: False)
	loc_size = 0
	def dfs(node):
		nonlocal loc_size 
		seen2[node] = True
		loc_size += 1
		for nbhr in G[node]:
			if seen2[nbhr]: continue
			dfs(nbhr)

	for i in range(n):
		if seen[i]: continue
		loc_size = 0
		dfs(i)
		sizes.append(loc_size)
	print(max(sizes))
	stdout.close()

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):#要素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):#print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
 

n, m  = map(int,input().split())
fri = []

uf = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    fri.append((a-1,b-1))

for a,b in fri:
    uf.union(a,b)
    
ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys

rln=lambda:next(sys.stdin)
rfs=lambda:rln().split()
ris=lambda:list(map(int,rfs()))

n,m=ris()
adj=[[] for _ in range(n)]
for _ in range(m):
    a,b=ris()
    a,b=a-1,b-1
    adj[a].append(b)
    adj[b].append(a)

ans=0
vis=[0]*n
for i in range(n):
    if vis[i]:
        continue
    vis[i]=1
    k=0
    stk=[i]
    while stk:
        u=stk.pop()
        k+=1
        for v in adj[u]:
            if vis[v]:
                continue
            vis[v]=1
            stk.append(v)
    ans=max(ans,k)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self):
        self.parents = {}
        self.sz = {}
        self.size = 0


    def add(self, a):
        if a in self.parents:
            return
        self.size += 1
        self.sz[a] = 1
        self.parents[a] = a 

    def find(self, a):
        if self.parents[a] != a:
            self.parents[a] = self.find(self.parents[a])

        return self.parents[a]

    def join(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return
        if self.sz[pa] > self.sz[pb]:
            self.parents[pb] = pa
            self.sz[pa] += self.sz[pb]
        else:
            self.parents[pa] = pb 
            self.sz[pb] += self.sz[pa]

        self.size -= 1


n,m = list(map(int,input().split(" ")))
uf = UnionFind()
ans = 0
if m == 0:
    print(1)
else:
    for _ in range(m):
        x,y = list(map(int,input().split(" ")))
        uf.add(x)
        uf.add(y)
        uf.join(x,y)
        ans = max(ans, uf.sz[x])

    print(max(uf.sz.values()))

Submission status: Accepted

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

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

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

        if x == y:
            return False
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

        return True
    

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


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

    UF = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A, B = A - 1, B - 1
        UF.unite(A, B)

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

    print(ans)

main()

Submission status: Accepted

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.size = [1]*n

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

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

        if x == y:
            return
        if self.size[x] > self.size[y]:
            x, y = y, x
        self.par[x] = y
        self.size[y] += self.size[x]


uf = UnionFind(N)

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

Submission status: Accepted

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

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

id_list = [-1]*n


def dfs(friends, start):
    d = deque()
    group_count = 0
    if id_list[start] == -1:
        id_list[start] = start
        d.append(start)
        group_count += 1
    while d:
        p = d.pop()
        for child in friends[p]:
            if id_list[child] != -1:
                continue
            group_count += 1
            id_list[child] = start
            d.append(child)
    return group_count

max_friend = 0
for i in range(n):
    max_friend = max(max_friend, dfs(friends, i))
print(max_friend)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dic = {}
for i in range(n):
    dic[i+1]=set()
    
for _ in range(m):
    a,b = map(int,input().split())
    dic[a].add(b)
    dic[b].add(a)

max_num = 0
registerd_set = set()
for i in range(1,n+1):
    if i in registerd_set:
        continue
    else:
        people_list = [i]
        registerd_set.add(i)
    count = 0
    for people in people_list:
        count += 1
        for friend in dic[people]:
            if friend not in registerd_set:
                registerd_set.add(friend)
                people_list.append(friend)
    if max_num < count:
        max_num = count
print(max_num)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, M, *AB = map(int, open(0).read().split())

uf = UnionFind(N + 1)
for a, b in zip(*[iter(AB)] * 2):
    uf.union(a, b)

print(max(uf.size(i) for i in range(1, N + 1)))

Submission status: Accepted

Solution code:

def dfs(u, g, visited):
    res = 0
    stack = [u]

    while(len(stack)):
        u = stack.pop()
        if (visited[u]): continue
        visited[u] = True
        res += 1

        for v in g[u]:
            stack.append(v)

    return res


def main():
    n,m = map(int, input().split())
    g = [ [] for _ in range(n+1) ]
    for _ in range(m):
        a,b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    visited = [False] * (n+1)
    ans = 0;
    for i in range(1, n+1):
        if (visited[i]): continue
        ans = max(ans, dfs(i, g, visited))

    print(ans)

main()