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
input = sys.stdin.readline
from collections import Counter


def read():
    N, M = list(map(int, input().strip().split()))
    AB = []
    for i in range(M):
        a, b = map(int, input().strip().split())
        AB.append((a, b))
    return N, M, AB


class UnionFind():
    """Union-Find木の実装
    """

    def __init__(self, n):
        self.n = n
        self.parent = [x for x in range(n)]

    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 union(self, x, y):
        """要素x, yがそれぞれ所属するグループを併合する
        """
        x = self.find(x)
        y = self.find(y)
        if x > y:
            x, y = y, x
        self.parent[y] = x

    def parents(self):
        """全てのノードについて、対応する親ノードを返す"""
        return [self.find(x) for x in range(self.n)]


def solve(N, M, AB):
    uf = UnionFind(N)
    for a, b in AB:
        uf.union(a-1, b-1)
    C = Counter(uf.parents())
    return C.most_common()[0][1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

root = [-1]*n#各数字の親を-1で初期化
def r(x):
    if root[x] < 0: #親がなければ自分自身の値を返す
        return x
    else:
        root[x] = r(root[x])#親を辿る
        return root[x]

def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:#親が同じ場合
        return
    root[x] += root[y]
    root[y] = x #xをyの親とする

for i in range(m):
    a, b = map(int, input().split())
    a -= 1#0_indexにする
    b -= 1
    unite(a, b)

ans = 0
for i in range(n):
    ans = max(ans, -root[i])#要素数が最大の親が答え

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

root = [-1]*n
def r(x):
    if root[x] < 0:
        return x
    else:
        root[x] = r(root[x])
        return root[x]

def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x

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

ans = 0
for i in range(n):
    ans = max(ans, -root[i])

print(ans)

Submission status: Accepted

Solution code:
class UnionFind(): # 0インデックス
    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とyは-=1して使う
        '''
        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)]


if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.size = [1 for i in range(N)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
            self.size[y] = self.size[x] + self.size[y] 

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

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

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

print(max(UF.size))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(1 << 25)  # 再起上限引き上げ

G = defaultdict(lambda: [])

#load data
N,M = map(int,input().split())
color = {key:0 for key in range(N)}
#graphをdefaultdictで保持することにする
for _ in range(M):
    s,t = map(int,input().split())
    G[s-1].append(t-1)
    G[t-1].append(s-1)
#print(G)
#隣接リストを基にたどり着ける友達をグループ化する。
def dfs(node:int, co:int):
    #終了条件、既に訪問済みなら訪問しない
    if color[node] != 0:
        return
    #処理
    color[node] = co
    for n in G[node]:
        dfs(n,co)

    return

#全てのnodeを開始点としてdfsで色分けしてみる
c = 1
for node in G.keys():
    dfs(node,c)
    c += 1

ans_list = [0]*(N)
for i in range(N):
    ans_list[color[i]] += 1

ans_list[0] = 0
if M == 0:
    print(1)
else:
    print(max(ans_list))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def DFS(i):
    if done[i]:
        ans[-1]+=1
        done[i]=False
        for g in G[i]:
            if done[g]:
                DFS(g)
    else:
        return p

N,M=map(int,input().split())
G=[[] for _ in range(N)]
done=[True for _ in range(N)]

for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=[]
for j in range(N):
    ans.append(0)
    if done[j]:
        DFS(j)
print(max(ans))

Submission status: Accepted

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]


n,m = readints()
u = UnionFind(n)
for i in range(m):
    a,b = (x-1 for x in readints())
    u.unite(a,b)

print(max([u.size(x) for x in range(n)]))

Submission status: Accepted

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

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

root = [-1]*n

def find(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find(root[x])
        return root[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 
    root[x] += root[y]
    root[y] = x

def size(x):
    x = find(x)
    return -root[x]

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

ans = 0
for i in range(n):
    ans = max(ans, size(i))

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 = 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

n,m = map(int,input().split())
par = [-1]*n
line = [0 for i in range(n)]
ans = 0
for i in range(m):
  a,b = map(int, input().split())
  unite(a-1,b-1)
for i in range(n):
  line[find(i)] += 1
  if line[find(i)] > ans:
    ans = line[find(i)]
print(ans)

Submission status: Accepted

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

n, m = map(int, input().split())
root = [-1] * n

def find_root(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find_root(root[x])
        return root[x]

def unite(x, y):
    x = find_root(x)  
    y = find_root(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x

def size(x):
    x = find_root(x)
    return -root[x]

for i in range(m):
    x, y = map(int,input().split())
    x -= 1
    y -= 1
    unite(x, y)

max_size = max(map(size, range(n)))

print(max_size)

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())
    a-=1
    b-=1
    uf.union(a, b)

ans =0
a = uf.roots()
for i in range(len(a)):
    if uf.size(a[i])>ans:
        ans = uf.size(a[i])
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    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_root = self.find(x)  # xの根
        y_root = self.find(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.find(x)]


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)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
A = [[] for i in range(N)]
checkd = [False]*N
for _ in range(M):
    a,b = (map(lambda a: int(a)-1, input().split()))
    A[a].append(b)
    A[b].append(a)
nextS = set(range(N))
ans = 0
while len(nextS)>0:
    s = nextS.pop()
    if checkd[s]: 
        continue
    count = 0
    que = deque([s])
    while len(que)>0:
        nn = que.popleft()
        if checkd[nn]:
            continue
        checkd[nn] = True
        nextS.discard(nn)
        count += 1
        que.extend(A[nn])
    ans = max(count,ans)


print(ans)

Submission status: Accepted

Solution code:
def find(target):
    if parent[target] < 0:
        return target
    else:
        parent[target] = find(parent[target])
        return parent[target]

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

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x
def members(n, x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

def get_size(x):
    return -parent[find(x)]

def get_root():
    return [i for i, root in enumerate(parent) if root < 0]
n, m = map(int, input().split())
parent = [-1 for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
    # print(parent)
ans = 0
for i in range(n):
    ans = max(ans, get_size(i))
print(ans)

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)

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(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, v):
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):
        u = self.find(u)
        v = self.find(v)

        if u == v:
            return

        if self.parents[u] > self.parents[v]:
            u, v = v, u

        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):
        return -self.parents[self.find(v)]

    def same(self, u, v):
        return self.find(u) == self.find(v)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class UnionFind:
    __slots__ = ['id','sz']

    def __init__(self, n):
        self.id = [-1] * n
        self.sz = n

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

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

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            self.sz-=1
            return True
        return False

n,m = map(int,input().split())
uf=UnionFind(n)
for i in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  
  uf.union(a,b)
M = 0
for i in range(n):
  M = min(M,uf.id[i])
print(abs(M))
# print(*uf.id)

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().split()]
l=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
# print(l)

done=[0]*n


def dfs(j):
  que=[j]
  cnt=1
  done[j]=1
  while(que):
    now=que.pop(0)

    for i in l[now]:
      if done[i]!=1:
        que.append(i)
        done[i]=1
        cnt+=1

  return cnt

ma=0
for j in range(n):
  if done[j]!=1:
    now=dfs(j)
  else:
    now=0
  ma=max(now,ma)
  
print(ma)

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {n: set() for n in range(N)}
remain_user = set()
for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    friends_map[a].add(b)
    friends_map[b].add(a)
    remain_user.add(a)
    remain_user.add(b)

stack = deque()
stack.appendleft(0)

max_group = 1
watch = set()
while stack:
    now = stack.popleft()

    if not now in watch:
        remain_user.discard(now)
        watch.add(now)

        for next_node in friends_map[now]:
            if not next_node in watch:
                stack.appendleft(next_node)

    if not stack:
        max_group = max(len(watch), max_group)

        if remain_user:
            stack.appendleft(remain_user.pop())
            watch = set()

print(max_group)

Submission status: Accepted

Solution code:

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n
    
    def find_root(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find_root(self.parents[x])
            return self.parents[x]
    def make_union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        
        if x == y : return
        self.size[x] += self.size[y]
        self.parents[y] = x

def main():
    n, m = map(int, input().split())
    uf = UnionFindPathCompression(n)
    for _ in range(m):
        a, b = map(int, input().split())
        uf.make_union(a - 1, b - 1)
    
    ans = max(uf.size)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {n : set() for n in range(N)}
remain_user = set()
for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    friends_map[a].add(b)
    friends_map[b].add(a)
    remain_user.add(a)
    remain_user.add(b)

stack = deque()
stack.appendleft(0)

max_group = 1
watch = [0] * N
count = 0
while stack:
    now = stack.popleft()

    if watch[now] == 0:
        remain_user.discard(now)
        watch[now] = 1
        count += 1

        for next_node in friends_map[now]:
            if watch[next_node] == 0:
                stack.appendleft(next_node)

    if not stack:
        max_group = max(count, max_group)

        if remain_user:
            stack.appendleft(remain_user.pop())
            count = 0

print(max_group)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 + 2 * 10 ** 5)
 
n, m = map(int, input().split())
 
color = [None] * (n + 1)
for i in range(n + 1):
    color[i] = i
 
def root(x):
    global color
 
    if color[x] == x:
        return x
    color[x] = root(color[x])
    return color[x]
 
def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    color[rx] = ry
 
for i in range(m):
    a, b = map(int, input().split())
    unite(a, b)
 
cnt = defaultdict(int)
for i in range(n):
    cnt[root(i + 1)] += 1
print(max(cnt.values()))

Submission status: Accepted

Solution code:
class union_find:
    def __init__(self, node_num):
        self.root_array = [-1] * node_num

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

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

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


def solve(n, m, ab_array):
    uf = union_find(n)
    for ab in ab_array:
        a, b = ab
        uf.unite(a - 1, b - 1)

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

    return ans

if __name__ == '__main__':
    n, m = map(int, input().split())
    ab_array = [list(map(int, input().split())) for _ in range(m)]
    ans = solve(n, m, ab_array)
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
par = [-1 for _ in range(n)]


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


def union(x, y):
    rx, ry = root(x), root(y)
    if rx == ry:
        pass
    else:
        if par[rx] > par[ry]:
            rx, ry = ry, rx
        par[rx] += par[ry]
        par[ry] = rx


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


for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
    
ans = 0
for i in range(n):
    ans = max(ans, size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


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


N, M = LI()
friend = [set() for _ in range(N)]
ans = 0
miru = set()
if M == 0:
    print(1)
    sys.exit()
for i in range(M):
    a, b = map(int, input().split())
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)
    miru.add(a-1)
    miru.add(b-1)
looked = [0]*N
d = deque()
count = 0
d.append(a-1)
miru.discard(a-1)
while d:
    x = d.pop()
    for i in friend[x]:
        if looked[i] != 0:
            continue
        count += 1
        looked[i] = 1
        d.append(i)

    if len(d) == 0:
        ans = max(count, ans)
        if len(miru) == 0:
            break
        y = miru.pop()
        d.append(y)
        looked[y] = 1
        count = 1
        miru.discard(y)

print(ans)

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-08-29 22:53
# @url:https://atcoder.jp/contests/abc177/tasks/abc177_d
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
from decimal import *
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192
sys.setrecursionlimit(10 ** 7)
class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    n,m=map(int,input().split())
    pairs=[]
    for i in range(m):
        a,b=map(int,input().split())
        temp=[]
        temp.append(a)
        temp.append(b)
        pairs.append(temp)
    fa=[i for i in range(n+1)]
    child=[1]*(n+1)
    def find(x):
        if x!=fa[x]:
            fa[x]=find(fa[x])
        return fa[x]
    def union(x,y):
        x = find(x)
        y = find(y)
        if x == y:  
            return
        fa[x] = y
        child[y]+=child[x]
    for (i,j) in pairs:
        union(i,j)
    # for (i,j) in pairs:
    #     union(j,i)
    # d=collections.Counter(fa)
    # print (child)
    # print (fa)
    print (max(child))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

    def bfs(n, m, adj):
        visited = [0 for i in [0]*(n+1)]
        ans = 1
        for i in range(n+1):
            if visited[i]:
                continue
            Q = deque([i])
            temp = 1
            while Q:
                q = Q.popleft()
                visited[q] = 1
                link = adj[q]
                for j in link:
                    if visited[j]:
                        continue
                    visited[j] = 1
                    temp += 1
                    Q.append(j)
            ans = max(ans, temp)
        print(ans)  
    bfs(n, m, g)
 
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
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
        
n,m = map(int,input().split())
a = [input().split() for l in range(m)]
uf = UnionFind(n)

for z in range(m):
    uf.union(int(a[z][0]), int(a[z][1]))
    
b = [0]*n

for r in range(1,n+1):
    b[uf.find(r)-1] += 1


print(max(b))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()

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 group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {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())
        uf.unite(a-1, b-1)
    roots = uf.roots()
    cnt = []
    for r in roots:
        cnt.append(uf.size(r))
    print(max(cnt))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N: int):
        self.parents = [-1] * N
        self.ranks = [-1] * N
        for i in range(N):
            self.ranks[i] = 0

    def find_root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            # find the root of x and make a shortcut pass
            self.parents[x] = self.find_root(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find_root(x)
        size_x = -self.parents[x]
        y = self.find_root(y)
        size_y = -self.parents[y]
        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y  # merge the tree under x to y
            self.parents[y] = -(size_x + size_y)
        else:
            self.parents[y] = x  # merge the tree under y to x
            self.parents[x] = -(size_x + size_y)
            # Rank of x increments (Note that the rank of the root doesn't change otherwise)
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1

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

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


def get_input():
    N, M = (int(x) for x in input().split())
    rels = []
    for m in range(M):
        r = [int(x) - 1 for x in input().split()]  # adjust to 0-origin
        rels.append(r)
    return N, M, rels


N, M, rels = get_input()

# Map friends on a union-find tree
tree = UnionFind(N)
for r in rels:
    x = r[0]
    y = r[1]
    if not tree.same(x, y):
        tree.unite(x, y)
# print(tree.parents)

# Max number of groups is the size of the largest group
max_size = 0
for i in range(N):
    s = tree.size(i)
    if max_size < s:
        max_size = s
print(max_size)