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: Wrong Answer

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

Co = [0]*(N+1)

cnt = 0
for i in range(M):
    a, b = map(int, input().split())
    A = Co[a]
    B = Co[b]
    if A == 0 and B == 0:
        cnt += 1
        Co[a] = cnt
        Co[b] = cnt
    elif A != 0 and B == 0:
        Co[b] = A
    elif A == 0 and B != 0:
        Co[a] = B
    else:
        x = max(A, B)
        y = min(A, B)
        for j in range(N+1):
            if Co[j] == x:
                Co[j] = y

del Co[0]
C = collections.Counter(Co)
ans = C.most_common()[0]
print(ans[1])

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
pairs = []
for i in [0]*M:
    inp = sorted(list(map(int,input().split())))
    if inp not in pairs:
        pairs.append(inp)
def solver(N,M,pairs):
    group_list = []
    max_len = -1
    for i in pairs:
        pair = sorted(i)
        for j in range(len(group_list)):
            if pair[1] in group_list[j]:
                break
            elif pair[0] in group_list[j]:
                group_list[j].append(pair[1])
                if max_len < len(group_list[j]):
                    max_len = len(group_list[j])
                break
        else:
            if max_len < 2:
                max_len = 2
            group_list.append(pair)
    return max_len
print(solver(N,M,pairs))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

check = [False] * N
ans = 0

for i in range(N):
  if check[i] == False:
    check[i] = True
    D = deque(friends[i])
    tmp = 1
    while D:
      f = D.popleft()
      if check[f] == False:
        check[f] = True
        tmp += 1
        for j in friends[i]:
          D.append(j)
    ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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

union = UnionFind(N)

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

ans = 0
c = Counter(union.par)

for k, v in c.items():
    ans = max(ans, v)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

R = defaultdict(int)

for _ in range(M):
    A, B = map(int, input().split())

    if R[A] == 0 and R[B] == 0:
        R[A] = A
        R[B] = A

    elif R[A] != 0 and R[B] != 0:
        pass

    elif R[A] == 0:
        R[A] = R[B]

    else: # R[B] == 0
        R[B] = R[A]


S = defaultdict(int)

for n in range(1, N+1):
    S[R[n]] += 1

print('{}'.format(max(S.items(), key=lambda item:item[1])[-1]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

R = defaultdict(int)

for _ in range(M):
    A, B = map(int, input().split())

    if R[A] == 0 and R[B] == 0:
        R[A] = A
        R[B] = A

    elif R[A] == 0:
        R[A] = R[B]

    else: # R[B] == 0
        R[B] = R[A]


S = defaultdict(int)

for n in range(1, N+1):
    S[R[n]] += 1

print('{}'.format(max(S.items(), key=lambda item:item[1])[-1]))

Submission status: Wrong Answer

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

friendship = [0] * (n+1)

set_mark = 0
for i in range(m):
  p1,p2 = map(int,input().split())
  if friendship[p1] == 0 and friendship[p2] == 0:
    set_mark += 1
    friendship[p1] = friendship[p2] = set_mark
  elif friendship[p1] == 0 and friendship[p2] != 0:
    friendship[p1] = friendship[p2]
  elif friendship[p2] == 0 and friendship[p1] != 0:
   	friendship[p2] = friendship[p1]
    
count = {}
for mark in friendship:
  if mark != 0:
    if mark not in count:
      count[mark] = 1
    else:
   	  count[mark] += 1
    
times = list(count.values())
if not times:
  print(1)
else:
  ans = max(times)
  print(ans)

Submission status: Wrong Answer

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

friendship = [0] * (n+1)

set_mark = 0
for i in range(m):
  p1,p2 = map(int,input().split())
  if friendship[p1] == 0 and friendship[p2] == 0:
    set_mark += 1
    friendship[p1] = friendship[p2] = set_mark
  elif friendship[p1] == 0 and friendship[p2] != 0:
    friendship[p1] = friendship[p2]
  elif friendship[p2] == 0 and friendship[p1] != 0:
   	friendship[p2] = friendship[p1]
    
count = {}
for mark in friendship:
  if mark not in count:
    count[mark] = 1
  else:
    count[mark] += 1
    
times = list(count.values())
ans = max(times)
print(ans)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
L = [set() for _ in range(N+1)]
T = [-1] * (N+1)
for i in range(M):
    A, B = map(int, input().split())
    L[A].add(B)
    L[B].add(A)

g = 0
group = 0
for i, l in enumerate(T):
    if i == 0:
        continue
    if l == -1:
        cnt = 1
        g += 1
        T[i] = g
        if L[i] != set():
            for j in L[i]:
                T[j] = g
                cnt += 1
        if cnt > group:
            group = cnt

print(group)

Submission status: Wrong Answer

Solution code:
#ABC177
#D - Friends

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

friends=[]
member=[]

for i in range(M):
  j=sorted(list(map(int,input().split())))
  if j not in friends:
    friends.append(j)
    member.extend(j)

member2=[i for i in set(member) if member.count(i)>1 ]
friends=[i for i in friends for j in i if j in member2]

for i in member2:
  a=[k for j in friends if i in j for k in j]
  c=[j for j in friends if i not in j]
  friends=[list(set(a))]+c
  
group=[len(i) for i in friends]    

if len(group)==0:
  print(1)
else:
  print(max(group))

Submission status: Wrong Answer

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

class unionfind():
    def __init__(self,n):
        self.li = [i for i in range(n+1)]
        self.group = [1]*(n+1)

    def find(self, x):
        while self.li[x]!=x:
            x = self.li[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return;
        else:
            self.li[y] = x
            self.group[x] += self.group[y]
            self.group[y] = 1
x = unionfind(n)
ans = 0
for _ in range(m):
    a,b = map(int,input().split())
    x.union(a,b)
print(max(x.group))
print(x.group)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

n,m=map(int, input().split())
uf=UnionFind(n)
for _ in range(m):
    a,b=map(int, input().split())
    uf.union(a-1, b-1)
cnt=0

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,Counter


graph = defaultdict(set)
n,m = map(int,input().split())

for i in range(m):
    u,v = map(int,input().split())
    graph[u].add(v)
    graph[v].add(u)

parent=list(i for i in range(n+1))

def findparent(parent,k):
    if parent[k]==k:
        return k
    return  findparent(parent,parent[k])

def union(x,y):
    if y>x:
        parent[y]=x
    else:
        parent[x]=y
count=0
i=0

for u in graph:
    x=findparent(parent,u)
    for v in graph[u]:
        y=findparent(parent,v)

        union(x,y)

d=Counter(parent[1:])
print(max(d.values()))

Submission status: Wrong Answer

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=list(map(int,input().split()))
g=UnionFind(n+1)
ans=0
for i in range(m):
    a,b=list(map(int,input().split()))
    g.union(-a,-b)

for i in range(n):
    ans=max(ans,g.size(i))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

g=defaultdict(set)
n,m=map(int,input().split())
count=n
visited = [False]*(n+1)
visited1=[False]*(n+1)
for i in range(m):
    u,v=map(int,input().split())
    if visited1[u]==False:
        visited1[u]=True
        count-=1
    if visited1[v]==False:
        visited1[v] = True
        count -= 1
    g[u].add(v)
    g[v].add(u)
def dfs(node):
    lst=[]
    queue=[]
    queue.append(node)
    while len(queue):
        node = queue.pop(0)
        if visited[node]:
            continue
        visited[node]=True
        lst.append(node)
        for i in g[node]:
            if not visited[i]:
                queue.append(i)

    return len(lst)

k=dfs(1)

for i in range(1,len(visited)):
    if not visited[i]:
        m=dfs(i)
        if m>k:
            k=m

print(max(count,k))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

g=defaultdict(set)
n,m=map(int,input().split())
visited = [True]*(n+1)
for i in range(m):
    u,v=map(int,input().split())
    visited[u]=False
    visited[v]=False
    g[u].add(v)
    g[v].add(u)

final=[]
def dfs(node):
    lst=[]
    queue=[]
    queue.append(node)
    while len(queue):
        node = queue.pop(0)
        if visited[node]:
            continue
        visited[node]=True
        lst.append(node)
        for i in g[node]:
            if not visited[i]:
                queue.append(i)

    return len(lst)

k=dfs(1)

for i in range(1,len(visited)):
    if not visited[i]:
        m=dfs(i)
        if m>k:
            k=m

print(k)

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

#sys.setrecursionlimit(30000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

m = {}
for i in range(M):
    if (T[i][0], T[i][1]) in m:
        continue
    m[(T[i][0], T[i][1])] = True
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

def search(n):
    ret = 1
    deq = deque()

    memo[n] = 1
    for t in dic[n]:
        if memo[t] == 0:
            memo[t] = 1
            deq.append(t)

    while len(deq) != 0:
        d = deq.popleft()
        ret += 1
        if memo[d] == 0:
            memo[d] = 1
            for t in dic[d]:
                deq.append(t)

    return ret

memo = array1(N)

ans = 0
for i in range(N):
    if memo[i] == 1:
        continue

    ans = max(search(i), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

#sys.setrecursionlimit(30000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

m = {}
for i in range(M):
    if (T[i][0], T[i][1]) in m:
        continue
    m[(T[i][0], T[i][1])] = True
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

#pprint(dic)

def search(n):
    ret = 1
    deq = deque()

    for t in dic[n]:
        if memo[t] == 0:
            memo[t] = 1
            deq.append(t)

    while len(deq) != 0:
        d = deq.popleft()
        ret += 1
        if memo[d] == 0:
            memo[d] = 1
            for t in dic[d]:
                deq.append(t)

    return ret

memo = array1(N)

ans = 0
for i in range(N):
    if memo[i] == 1:
        continue

    ans = max(search(i), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

#sys.setrecursionlimit(30000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

for i in range(M):
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

def search(n):
    ret = 1
    deq = deque()

    for t in dic[n]:
        if memo[t] == 0:
            memo[t] = 1
            deq.append(t)

    while len(deq) != 0:
        d = deq.popleft()
        ret += 1
        if memo[d] == 0:
            memo[d] = 1
            for t in dic[d]:
                deq.append(t)

    return ret

memo = array1(N)

ans = 0
for i in range(N):
    if memo[i] == 1:
        continue

    tmp = search(i)
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


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")
##########################################################
from collections import Counter
# c=sorted((i,int(val))for i,val in enumerate(input().split()))
import heapq
# c=sorted((i,int(val))for i,val in enumerate(input().split()))
# n = int(input())
# ls = list(map(int, input().split()))
#n=int(input())
#arr = list(map(int, input().split()))

#for _ in range(int(input())):

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


def unioin(x,y):
    uroot=find(u,root)

    vroot=find(v,root)

    if uroot!=vroot:
        if rank[uroot]>rank[vroot]:
            root[vroot]=root[uroot]
            rank[uroot]+=1
        elif rank[vroot]>rank[uroot]:
            root[uroot]=root[vroot]
            rank[vroot]+=1
        else:
            rank[uroot]+=1
            root[vroot]=root[uroot]




n,m= map(int, input().split())
rank=[1]*(n+1)
root=[i for i in range(n+1)]
for i in range(m):
    u,v = map(int, input().split())
    unioin(u,v)
ans=0
print(max(rank))

Submission status: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


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")
##########################################################
from collections import Counter
# c=sorted((i,int(val))for i,val in enumerate(input().split()))
import heapq
# c=sorted((i,int(val))for i,val in enumerate(input().split()))
# n = int(input())
# ls = list(map(int, input().split()))
#n=int(input())
#arr = list(map(int, input().split()))

#for _ in range(int(input())):

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


def unioin(x,y):
    uroot=find(u,root)

    vroot=find(v,root)

    if uroot!=vroot:
        if rank[uroot]>rank[vroot]:
            root[vroot]=root[uroot]
            rank[uroot]+=1
        elif rank[vroot]>rank[uroot]:
            root[uroot]=root[vroot]
            rank[vroot]+=1
        else:
            rank[uroot]+=1
            root[vroot]=root[uroot]




n,m= map(int, input().split())
rank=[1]*(n+1)
root=[i for i in range(n+1)]
for i in range(m):
    u,v = map(int, input().split())
    unioin(u,v)
ans=0
for i in range(n):
    ans=max(ans,rank[root[i+1]])
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


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")
##########################################################
from collections import Counter
# c=sorted((i,int(val))for i,val in enumerate(input().split()))
import heapq
# c=sorted((i,int(val))for i,val in enumerate(input().split()))
# n = int(input())
# ls = list(map(int, input().split()))
#n=int(input())
#arr = list(map(int, input().split()))

#for _ in range(int(input())):

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


def unioin(x,y):
    uroot=find(u,root)

    vroot=find(v,root)

    if uroot!=vroot:
        if rank[uroot]>rank[vroot]:
            root[vroot]=root[uroot]
            rank[uroot]+=1
        elif rank[vroot]>rank[uroot]:
            root[uroot]=root[vroot]
            rank[vroot]+=1
        else:
            rank[uroot]+=1
            root[vroot]=root[uroot]




n,m= map(int, input().split())
rank=[1]*(n+1)
root=[i for i in range(n+1)]
for i in range(m):
    u,v = map(int, input().split())
    unioin(u,v)
ans=0
for i in range(n):
    ans=max(ans,rank[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import copy

#function
def check_root(forest,leaf):
  #print(forest,leaf)
  if not forest[leaf]== leaf:
    return check_root(forest,forest[leaf])
  else:
    return leaf
  
def reset_tree(forest):
  forest_copy = copy.copy(forest)
  for i in range(len(forest)):
    forest_copy[i]=check_root(forest,i)
  return forest_copy

def check_same(forest,leaf1,leaf2):
  if(check_root(forest,leaf1)==check_root(forest,leaf2)):
    return True
  else:
    return False
  

def connect_tree(forest,rx,ry):
  if forest.count(rx)<forest.count(ry):
    forest[rx]=ry
  else:
    forest[ry]=rx
  reset_tree(forest)
  return forest
  
#input
N,M =map(int,stdin.readline().split())
abc = [list(map(int,stdin.readline().split())) for _ in range(M)]
abc = list(map(lambda  abc_v:list(map(lambda x: x-1,abc_v)),abc))
forest = list(range(N))

#main
for i in range(M):
  temp1 =check_root(forest,abc[i][0])
  temp2 = check_root(forest,abc[i][1])
  #if check_same(forest,abc[i][0],abc[i][1]):
  if temp1==temp2:
    continue
  else:
    forest = connect_tree(forest,temp1,temp2)
    #forest = connect_tree(forest,check_root(forest,abc[i][0]),check_root(forest,abc[i][1]))

                          
max_num = 0
for i in range(N):
  temp = forest.count(i)
  if max_num<temp:
    max_num=temp
    

print(max_num)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import copy

#function
def check_root(forest,leaf):
  #print(forest,leaf)
  if not forest[leaf]== leaf:
    return check_root(forest,forest[leaf])
  else:
    return leaf
  
def reset_tree(forest):
  forest_copy = copy.copy(forest)
  for i in range(len(forest)):
    forest_copy[i]=check_root(forest,i)
  return forest_copy

def check_same(forest,leaf1,leaf2):
  if(check_root(forest,leaf1)==check_root(forest,leaf2)):
    return True
  else:
    return False
  

def connect_tree(forest,rx,ry):
  if forest.count(rx)<forest.count(ry):
    forest[rx]=ry
  else:
    forest[ry]=rx
  reset_tree(forest)
  return forest
  
#input
N,M =map(int,stdin.readline().split())
abc = [list(map(int,stdin.readline().split())) for _ in range(M)]
abc = list(map(lambda  abc_v:list(map(lambda x: x-1,abc_v)),abc))
forest = list(range(N))

#main
for i in range(M):
  if check_same(forest,abc[i][0],abc[i][1]):
    continue
  else:
    forest = connect_tree(forest,check_root(forest,abc[i][0]),check_root(forest,abc[i][1]))

                          
max_num = 0
for i in range(N):
  temp = forest.count(i)
  if max_num<temp:
    max_num=temp
    

print(max_num)

Submission status: Wrong Answer

Solution code:
#D - Friends
N,M = map(int,input().split())
par = [i for i in range(N+1)]
rank = [1] * (N + 1)

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]

def size(x):
    return par.count(find(x))

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if x > y:
        x,y = y,x
    par[y] = x
    if par[x] == par[y]:
        rank[x] += 1
#    par[x] = y

#print(par)
#print(rank)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
#    print(par)
#    print(rank)
group_count = 0

group_count = max(rank)

# 出力
print(group_count)

Submission status: Wrong Answer

Solution code:
from collections import deque
 
N, M = map(int, input().split())
g = {i:set() for i in range(N)}
v = [-1 for i in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[min(a,b)].add(max(a,b))
  
Q = deque()
ans = 0
for a in g:
  if v[a]==-1:
    v[a] = 1
    ans_tmp = 1
    Q.append(a)
    while len(Q)>0:
      na = Q.popleft()
      for nb in g[na]:
        if v[nb] == -1:
          v[nb] = 1
          ans_tmp += 1
          Q.append(nb)
    ans = max(ans, ans_tmp)
print(ans)