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

num_group = len(set(uf.parents))-1
print(num_group)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
t = dict()
for i in range(1, n+1):
    t[i] = set()
for a, b in ab:
    t[a].add(b)
    t[b].add(a)

s = set()
ans = 0
for i in range(1, n+1):
    if i not in s:
        s.add(i)
        tmp = [i]
        for ti in t[i]:
            if ti not in s:
                tmp.append(ti)
                s.add(ti)
        ans = max(ans, len(tmp))
print(ans)

Submission status: Wrong Answer

Solution code:
number = [int(s) for s in input().split()]
input = [[int(x) for x in input().split()] for i in range(number[1])]
team = 0
check = [0]*number[1]

for i in range(number[1]):
    if(check[i] == 0):
        check[i] = 1
        init = set(input[i])
        for j in range(number[1]):
            if(j != i) & (len(init & set(input[j])) != 0) & (check[j] == 0):
                init = init | set(input[j])
                check[j] = 1
        if(len(init) > team):
            team = len(init)

print(team)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [[] for _ in range(n + 1)]
ans = 0
for i in range(m):
    a,b = map(int, input().split())
    if a not in ab[b]:
        ab[b].append(a)
    if b not in ab[a]:
        ab[a].append(b)
flag_visited = [False] * (n + 1)
newly_visited = []
ans = 0
for i in range(n):
    length = 0
    if flag_visited[i] == False:
        for j in range(len(ab[i])):
            if flag_visited[ab[i][j]] == False:
                newly_visited.append(ab[i][j])
                while len(newly_visited) > 0:
                    now = newly_visited.pop()
                    # print(now)
                    # print(ab)
                    # print(ab[now])
                    if flag_visited[ab[i][j]] == True:
                        continue
                    for k in ab[now]:
                        newly_visited.append(k)
                    flag_visited[ab[i][j]] = True
                    length += 1
            if length > ans:
                ans = length
print(ans+ 1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
t = dict()
for i in range(1, n+1):
    t[i] = set()
for a, b in ab:
    t[a].add(b)
    t[b].add(a)

s = set()
ans = 0
for i in range(1, n+1):
    if i not in s:
        s.add(i)
        tmp = [i]
        for ti in t[i]:
            if ti not in s:
                tmp.append(ti)
                s.add(ti)
    ans = max(ans, len(tmp))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

graph = [[] for _ in range(n + 1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

for i in range(len(graph)):
    graph[i] = list(set(graph[i]))

ans = 0
for l in graph:
    if not l:
        continue

    isfriend = [False] * (n + 1)
    q = deque(l)
    while q:
        now = q.popleft()
        for i in graph[now]:
            if isfriend[i] == False:
                isfriend[i] = True
                q.append(i)
    ans = max(ans, sum(isfriend))

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(a) for a in input().split()]
lol = []
grp = {k:-10 for k in range(1,N+1)}
for i in range(M):
  a, b = [int(a) for a in input().split()]
  found_a = grp[a]
  found_b = grp[b]
  
  if found_a < 0 and found_b < 0:
    lol.append({a,b})
    grp[a] = len(lol) - 1
    grp[b] = len(lol) - 1
  elif found_a >= 0 and found_b < 0:
    lol[found_a].add(b)
    grp[b] = grp[a]
  elif found_b >= 0 and found_a < 0:
    lol[found_b].add(a)
    grp[a] = grp[b]
  elif found_a >= 0 and found_b >= 0 and found_a != found_b:
    lol[found_a].update(lol[found_b])
    #lol.pop(found_b)
    for k in lol[found_b]:
      grp[k] = grp[a]

   
ans = -1
if M == 0 or len(lol) == 0:
  ans = N
else:
  for z in lol:
    if len(z) > ans:
      ans = len(z)

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(a) for a in input().split()]
lol = []
grp = {k:-10 for k in range(1,N+1)}
for i in range(M):
  a, b = [int(a) for a in input().split()]
  found_a = grp[a]
  found_b = grp[b]
  
  if found_a < 0 and found_b < 0:
    lol.append({a,b})
    grp[a] = len(lol) - 1
    grp[b] = len(lol) - 1
  elif found_a >= 0 and found_b < 0:
    lol[found_a].add(b)
    grp[b] = grp[a]
  elif found_b >= 0 and found_a < 0:
    lol[found_b].add(a)
    grp[a] = grp[b]
  elif found_a >= 0 and found_b >= 0 and found_a != found_b:
    lol[found_a].update(lol[found_b])
    #lol.pop(found_b)
    for k in lol[found_b]:
      grp[k] = grp[a]
    
ans = -1
for z in lol:
  if len(z) > ans:
    ans = len(z)

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
rel = [ [] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if rel[a].count(b) == 0:
        rel[a].append(b)
        rel[a] += rel[b]
        rel[a] = list(set(rel[a]))
    if rel[b].count(a) == 0:
        rel[b].append(a)
        rel[b] += rel[a]
        rel[b] = list(set(rel[b]))

ans = 0
for i in rel:
    ans = max(ans,len(i))
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(a) for a in input().split()]
lol = []
for i in range(M):
  a, b = [int(a) for a in input().split()]
  found_a = -10
  found_b = -10
  for j in range(len(lol)):
    if a in lol[j]:
      found_a = j
    if b in lol[j]:
      found_b = j
    if found_a >= 0 and found_b >= 0:
      break
  
  if found_a < 0 and found_b < 0:
    lol.append({a,b})
  elif found_a >= 0 and found_b < 0:
    lol[found_a].add(b)
  elif found_b >= 0 and found_a < 0:
    lol[found_b].add(a)
  elif found_a >= 0 and found_b >= 0 and found_a != found_b:
    lol[found_a].update(lol[found_b])
    lol.pop(found_b)
    
ans = -1
for z in lol:
  if len(z) > ans:
    ans = len(z)

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
data = []
for i in range(m):
    a, b = list(map(int, input().split()))
    find = False
    for j in range(len(data)):
        if a in data[j] and not(b in data[j]):
            data[j].append(b)
            find = True
            break
        elif b in data[j] and not(a in data[j]):
            data[j].append(a)
            find = True
            break

    if find == False:
        data.append([a, b])

ans = 0
for i in range(len(data)):
    if len(data[i]) > ans:
        ans = len(data[i])

print(ans)

Submission status: Wrong Answer

Solution code:
from networkx import *
n,m = map(int, input().split())
if m == 0: print(1);exit()
G = Graph()
for i in range(m):
    a,b = map(int, input().split())
    G.add_edges_from([(a,b)])

print(len(max(connected_components(G))))

Submission status: Wrong Answer

Solution code:
import copy
import sys
from collections import deque
N, M = map(int,input().split())
checked = [False for _ in range(N)]
path = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = list(map(lambda x: int(x)-1, s.split()))
    path[a].append(b)
    path[b].append(a)
dq = deque([[i,i] for i in range(N)])
friends = [[i] for i in range(N)]
while dq:
   i, num= dq.popleft()
   if checked[i]:
      continue
   checked[i] = True
   for j in range(len(path[i])):
      h = path[i][j]
      if not checked[h]:
         dq.appendleft([h, num])
         friends[num].append(h)
ans = 0
for i in range(N):
   number = len(friends[i])
   ans = max(ans, number)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import sys
from collections import deque
N, M = map(int,input().split())
checked = [False for _ in range(N)]
path = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = list(map(lambda x: int(x)-1, s.split()))
    path[a].append(b)
    path[b].append(a)
dq = deque([[i,i] for i in range(N)])
friends = [[i] for i in range(N)]
while dq:
   i, num= dq.popleft()
   if checked[i]:
      continue
   checked[i] = True
   for j in range(len(path[i])):
      h = path[i][j]
      if not checked[h]:
         dq.appendleft([h, num])
         friends[num].append(h)
ans = -1
for i in range(N):
   number = len(friends[i])
   ans = max(ans, number)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import sys
from collections import deque
N, M = map(int,input().split())
checked = [False] * N
dq = deque([0])
path = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = list(map(lambda x: int(x)-1, s.split()))
    path[a].append(b)
    path[b].append(a)
dq = deque([[i,i] for i in range(N)])
friends = [[i] for i in range(N)]
while dq:
   i, num= dq.popleft()
   if checked[i]:
      continue
   checked[i] = True
   for j in range(len(path[i])):
      h = path[i][j]
      if not checked[h]:
         dq.appendleft([h, num])
         friends[num].append(h)
ans = -1
for i in range(N):
   number = len(friends[i])
   ans = max(ans, number)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import sys
from collections import deque
N, M = map(int,input().split())
checked = [False] * N
dq = deque([0])
path = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = list(map(lambda x: int(x)-1, s.split()))
    path[a].append(b)
    path[b].append(a)
dq = deque([[i,i] for i in range(N)])
friends = [[] for i in range(N)]
while dq:
   i, num= dq.popleft()
   if checked[i]:
      continue
   checked[i] = True
   for j in range(len(path[i])):
      h = path[i][j]
      if not checked[h]:
         dq.appendleft([h, num])
         friends[num].append(h)
ans = -1
for i in range(N):
   number = len(friends[i])
   ans = max(ans, number)
print(ans+1)

Submission status: Wrong Answer

Solution code:
import copy
import sys
from collections import deque
N, M = map(int,input().split())
checked = [False] * N
dq = deque([0])
path = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = list(map(lambda x: int(x)-1, s.split()))
    path[a].append(b)
    path[b].append(a)
dq = deque([[i,i] for i in range(N)])
friends = [[] for i in range(N)]
while dq:
   i, num= dq.popleft()
   if checked[i]:
      continue
   checked[i] = True
   for j in range(len(path[i])):
      h = path[i][j]
      if not checked[h]:
         dq.appendleft([h, num])
         friends[num].append(h)
ans = -1
for i in range(N):
   number = len(friends[i])
   ans = max(ans, number)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
friends_groups = []
for m in range(M):
    a, b = [int(i) for i in input().split()]
    flag = True
    for group in friends_groups:
        if a in group or b in group:
            group.add(a)
            group.add(b)
            flag = False
            break
    if flag :
        new_group = {a, b}
        friends_groups.append(new_group)

output = 0
for group in friends_groups:
    if len(group) > output:
        output = len(group)

print(output)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [[] for _ in range(n + 1)]
ans = 0
if m == 0:
    print(1)
    exit()
for i in range(m):
    a,b = map(int, input().split())
    if a not in ab[b]:
        ab[b].append(a)
    if b not in ab[a]:
        ab[a].append(b)
for i in range(1, n + 1):
    length = len(ab[i])
    if length > ans:
        ans =length
print(ans + 1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
friend = [0]*n
for i in range(n):
    friend[i] = list()
# print(friend)
for i in range(m):
    a,b = map(int,input().split())
    if not(b-1 in friend[a-1]):
        friend[a-1].append(b-1)
    if not(a-1 in friend[b-1]):
        friend[b-1].append(a-1)
# print(friend)
manyfriend = -1
for i in range(n):
    manyfriend = max(len(friend[i]),manyfriend)
print(manyfriend+1)

Submission status: Wrong Answer

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

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

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

N,M = map(int, input().split())
root = [-1]*N
for _ in range(M):
    a,b = map(lambda x: int(x) - 1, input().split())
    union(a,b)

root_dict = defaultdict(lambda: 0)
for i in range(N):
    key = root[i]
    if key < 0:
        root_dict[i] += 1
    else:
        root_dict[key] += 1
print(max(root_dict.values()))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data)

class UF:
    def __init__(self, N):
        self._id = list(range(N))
        self._count = N
        self._rank = [0] * N
    def find(self, p):
        id = self._id
        while p != id[p]:
            p = id[p] = id[id[p]]
        return p
    def union(self, p, q):
        id = self._id
        rank = self._rank
        i = self.find(p)
        j = self.find(q)
        if i == j:
            return
        self._count -= 1
        if rank[i] < rank[j]:
            id[i] = j
        elif rank[i] > rank[j]:
            id[j] = i
        else:
            id[j] = i
            rank[i] += 1


ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, m = I()

uf = UF(n)
for _ in range(m):
    a, b = I()
    uf.union(a-1, b-1)

ans = D(int)
for i in range(n):
    ans[uf.find(i)] += 1

print(max(ans.values()))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data)

class UF:
    def __init__(self, N):
        self._id = list(range(N))
        self._count = N
        self._rank = [0] * N
    def find(self, p):
        id = self._id
        while p != id[p]:
            p = id[p] = id[id[p]]
        return p
    def union(self, p, q):
        id = self._id
        rank = self._rank
        i = self.find(p)
        j = self.find(q)
        if i == j:
            return
        self._count -= 1
        if rank[i] < rank[j]:
            id[i] = j
        elif rank[i] > rank[j]:
            id[j] = i
        else:
            id[j] = i
            rank[i] += 1


ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, m = I()

uf = UF(n)
for _ in range(m):
    a, b = I()
    uf.union(a-1, b-1)

ans = D(int)
for i in range(n):
    ans[uf.find(i)] += 1

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
myFriend = [[i] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    myFriend[a].append(b)
    myFriend[b].append(a)
#print(myFriend)
ans = 0
for i in range(len(myFriend)):
    tmp = len(list(set(myFriend[i])))
    ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import copy
def set_union(pre_list):
  #print("set_union")
  post_list=[]
  
  for i in range(len(pre_list)):
    flag=0
    for j in range(len(post_list)):
      if(post_list[j]==pre_list[i]):
        flag=1
        break
    if flag==0:
      post_list.append(pre_list[i])
      
  return post_list
    



N,M =map(int,stdin.readline().split())
abc = [list(map(int,stdin.readline().split())) for _ in range(M)]
friend = []
group = 2
index_M = list(range(M))
pre_index_M = copy.copy(index_M)

while (len(pre_index_M)>0):
  #print(index_M)
  #print(pre_index_M)
  for i in range(len(pre_index_M)):
    flag=0
    for j in range(len(friend)):
      for k in friend[j]:
        if k == abc[pre_index_M[i]][0] or k == abc[pre_index_M[i]][1]:
          friend[j].extend(abc[pre_index_M[i]])
          #print(set_union(friend[j]))
          friend[j]=set_union(friend[j])
          flag = 1
          #print(i)
          #print(index_M)
          del index_M[i]
          break
      else:
        continue
      break
    else:
      continue
    break
  if flag==0:
    friend.append(abc[index_M[0]])
    del index_M[0]
    #print("friend",friend)
  pre_index_M=copy.copy(index_M)
  
max_num = 0

for i in friend:
  if len(i) > max_num:
    max_num = len(i)

#print(friend)
print(max_num)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
f = [set([i]) for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    for i in f[a-1]:
        if i != a-1:
            f[i].add(b-1)
    f[a-1].add(b-1)
    for j in f[b-1]:
        if j != b-1:
            f[j].add(a-1)
    f[b-1].add(a-1)
ans = 0
for fri in f:
    ans = max(ans, len(fri))
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
bg = [-1] * n
gn = -1
grp = []
if m == 0:
    print(1)
else:
    for _ in range(m):
        a, b = map(int, input().split())
        if bg[a - 1] == -1 and bg[b - 1] == -1:
            grp.append({a,b})
            gn += 1
            bg[a - 1], bg[b - 1] = gn, gn
        elif bg[a - 1] == -1:
            grp[bg[b - 1]].add(a)
            bg[a - 1] = bg[b - 1]
        elif bg[b - 1] == -1:
            grp[bg[a - 1]].add(b)
            bg[b - 1] = bg[a - 1]
    ans = 0
    for i in grp:
        ans = max(ans, len(i))
    print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
f = [set() for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    for i in f[a-1]:
        if i != a-1:
            f[i].add(b-1)
    f[a-1].add(b-1)
    for j in f[b-1]:
        if j != b-1:
            f[j].add(a-1)
    f[b-1].add(a-1)

g = [0 for _ in range(n)]
cnt = 0
for i in range(n):
    if g[i]:
        continue
    else:
        g[i] = 1
        group = f[i]
        fri = [i]
        for j in range(i+1, n):
            if j not in group and g[j] == 0:
                g[j] = 1
                group = group.union(f[j])
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int,input().split())
par = [i for i in range(N+1)]
rank = [0] * (N+1)

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
 # 併合
def union(x, y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    #print(par)
    # 同じ集合に属するか判定
def same_check(x, y):
    return find(x) == find(y)
mylist = []    
for m in range(M):
    a, b = map(int, input().split())
    mylist += [[a, b]]
    #union(a,b)
#print(mylist)
mylist.sort()
#print(mylist)
#or n in range(1,N+1):
for m in range(M):
    a, b = mylist[m]
    union(a, b)
#print(par)
mymax = 0
rank = [0] * (N+1)
for n in range(N+1):
    rank[par[n]] += 1
print(max(rank))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
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
def size(x):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())

    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i+1))
print(ans)
print(root)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
bg = [-1] * n
gn = 0
grp = []
if m == 0:
    print(1)
else:
    a, b = map(int, input().split())
    grp.append({a,b})
    bg[a - 1], bg[b - 1] = gn, gn
    for _ in range(m - 1):
        a, b = map(int, input().split())
        if bg[a - 1] == -1 and bg[b - 1] == -1:
            grp.append({a,b})
            gn += 1
            bg[a - 1], bg[b - 1] = gn, gn
        elif bg[a - 1] == -1:
            grp[bg[b - 1]].add(a)
            bg[a - 1] = bg[b - 1]
        elif bg[b - 1] == -1:
            grp[bg[a - 1]].add(b)
            bg[b - 1] = bg[a - 1]
    ans = 0
    for i in grp:
        ans = max(ans, len(i))
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int,input().split())
par = [i for i in range(N+1)]
rank = [0] * (N+1)

def find(x):
    if par[x] == x:
        return x
    else:
        # 走査していく過程で親を書き換える
        par[x] = find(par[x])
        return par[x]
#x = find(1)
 # 併合
def union(x, y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    # 同じ集合に属するか判定
def same_check(x, y):
    return find(x) == find(y)
    
for m in range(M):
    a, b = map(int, input().split())
    union(a,b)
#print(par)
#or n in range(1,N+1):
mymax = 0
rank = [0] * (N+1)
for n in range(N+1):
    rank[par[n]] += 1
print(max(rank))

Submission status: Wrong Answer

Solution code:
from sys import stdin
N,M =map(int,stdin.readline().split())
abc = [list(map(int,stdin.readline().split())) for _ in range(M)]
friend = []
group = 2
for i in range(M):  
  flag1 = 0
  for j in range(len(friend)):
    for k in friend[j]:
      temp=0
      if  k == abc[i][0] or k == abc[i][1]:
        if k == abc[i][0]:
          temp = 1
        else:
          temp = 0
        flag1+=1
    if(flag1==1):
        friend[j].append(abc[i][temp])
        flag1 = 1
        break
    else:
      break
  if(flag1==0):
    friend.append([abc[i][0],abc[i][1]])
      
        
max_num = 0

for i in friend:
  if len(i) > max_num:
    max_num = len(i)


print(max_num)

Submission status: Wrong Answer

Solution code:
from sys import stdin
N,M =map(int,stdin.readline().split())
abc = [list(map(int,stdin.readline().split())) for _ in range(M)]
friend = []
group = 2
for i in range(M):  
  flag1 = 0
  for j in range(len(friend)):
    for k in friend[j]:
      temp=0
      if  k == abc[i][0] or k == abc[i][1]:
        if k == abc[i][0]:
          temp = 1
        else:
          temp = 0
        flag1+=1
    if(flag1==1):
      if  k == abc[i][0] or k == abc[i][1]:
        friend[j].append(abc[i][temp])
        flag1 = 1
        break
    else:
      break
  if(flag1==0):
    friend.append([abc[i][0],abc[i][1]])
      
        
max_num = 0

for i in friend:
  if len(i) > max_num:
    max_num = len(i)


print(max_num)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
ab = [set(map(int, input().split())) for _ in range(m)]
ans = 0

for i in range(m):
    union = ab[i]
    for j in range(i-1, -m-1, -1):
        if not union.isdisjoint(ab[j]):
            union |= ab[j]
    if ans < len(union):
        ans = len(union)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int,input().split())
#mymap = [ [] for n in range(N) ]
par = [i for i in range(N+1)]
rank = [0] * (N+1)
#print(par)
def find(x):
    if par[x] == x:
        return x
    else:
        # 走査していく過程で親を書き換える
        par[x] = find(par[x])
        return par[x]
x = find(1)
#print(x)
 # 併合
def union(x, y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    # 同じ集合に属するか判定
def same_check(self, x, y):
    return find(x) == find(y)
    
for m in range(M):
    a, b = map(int, input().split())
    union(a,b)
#print(par)
#or n in range(1,N+1):
mymax = 0
rank = [0] * (N+1)
for n in range(N+1):
    rank[par[n]] += 1
print(max(rank))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(int,input().split())
    
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(N)
answer = 0
for i in range(M):
    uf.union(A[i]-1,B[i]-1)
    answer = max(answer,uf.size(A[i]-1))
if M == 0:
    answer = N
print(answer)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(int,input().split())
    
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(N)
answer = 0
for i in range(M):
    uf.union(A[i]-1,B[i]-1)
    answer = max(answer,uf.size(A[i]-1))
print(answer)

Submission status: Wrong Answer

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

dic = {}
for i in range(m):
  a, b = map(int, input().split())
  if not a in dic:
    dic[a] = [b]
  else:
    dic[a].append(b)
  if not b in dic:
    dic[b] = [a]
  else:
    dic[b].append(a)
max_ = 0
for k in dic:
  max_ = max(len(dic[k])+1, max_)
print(max_)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
dic = {}  # 各人が何番グループに属しているか
num = {}  # 各グループに何人属しているか
count = 0  # グループの番号

if M == 0:
    print(1)
    exit()

for _ in range(M):
    a, b = map(int, input().split())
    if a in dic and b not in dic:
        dic[b] = dic[a]
        num[dic[a]] += 1
    elif a not in dic and b in dic:
        dic[a] = dic[b]
        num[dic[b]] += 1
    elif a not in dic and b not in dic:  # どちらもグループに属していない場合、新たなグループを作る
        dic[a] = count
        dic[b] = count
        num[count] = 2
        count += 1

print(max(num.values()))