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:
def main():
  n, m = map(int, input().split())
  friends = [[] for _ in range(n)]
  for i in range(m):
    a, b = map(int, input().split())
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)
  ans = 1
  for i in range(n):
    ans = max(ans, len(set(friends[i])) + 1)
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


root = list(range(n + 1))


# from collections import defaultdict
# d = defaultdict(set)
cnt = [1] * (n + 1)


def find(i):
    if i == root[i]:
        return i
    root[i] = find(root[i])
    return root[i]

def union(u, v):
    fu, fv = find(u), find(v)
    if fu == fv:
        return
    root[max(u, v)] = min(fu, fv)
    cnt[min(fu, fv)] += cnt[max(u, v)]



for i in range(m):
    u, v = map(int, input().split())
    union(u, v)



# print(d)
print(max(cnt))

Submission status: Wrong Answer

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

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 -self.parents[self.find(x)]

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return -self.parents[self.find(x)]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)
    ans = 0
    if M == 0:
        print(N)
        return

    for i in range(M):
        x, y = map(int, input().split())
        ans = max(uf.union(x,y), ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(0,n+1)]
# print(par)
s = list()

# union find(parには0も入れているので、par[1]=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 x == y:
        return 0
    else:
        par[x] = y

# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a,b)
print(1)
# # 1～nの親を探してsに入れていき、一番多い親を答えにする
# for k in range(1,n+1):
#     s.append(find(k))
# # print(s)
# c = collections.Counter(s)
# print(max(c.values()))

Submission status: Wrong Answer

Solution code:
# 方針　union findで解く
n, m = map(int, input().split())  # 入力の受け取り
par = [i for i in range(1, n + 1)]  # 親のリストを作成


# find関数を作成。自分の値とリスト番号を比べ、親ならば返し、子ならば親を探す
# par[x-1]としているのは、例えばpar[0]=1になっているため
def find(x):
    if par[x - 1] == x:
        return x
    else:
        par[x - 1] = find(par[x - 1])
        return par[x - 1]


# union関数を作成。2つの引数の親を比べ、違う場合は一方の親を一方の子にする
def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x - 1] = y


# 入力すべてでunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a, b)
print(1)

# n人の親を探して、リストsに入れ、それぞれ親の数をカウントし、最頻値をグループ数とする。
#s = [find(i) for i in range(1, n + 1)]
#import collections
#c = collections.Counter(s)
#print(max(c.values()))

Submission status: Wrong Answer

Solution code:
# 方針　union findで解く
n, m = map(int, input().split())  # 入力の受け取り
par = [i for i in range(1, n + 1)]  # 親のリストを作成


# find関数を作成。自分の値とリスト番号を比べ、親ならば返し、子ならば親を探す
# par[x-1]としているのは、例えばpar[0]=1になっているため
def find(x):
    if par[x - 1] == x:
        return x
    else:
        par[x - 1] = find(par[x - 1])
        return par[x - 1]


# union関数を作成。2つの引数の親を比べ、違う場合は一方の親を一方の子にする
def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x - 1] = y


# 入力すべてでunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a, b)

# n人の親を探して、リストsに入れ、それぞれ親の数をカウントし、最頻値をグループ数とする。
#s = [find(i) for i in range(1, n + 1)]
import collections
c = collections.Counter(par)
print(max(c.values()))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
path = [set() for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1].add(b-1)
    path[b-1].add(a-1)
visited = [0] * N

ans = 1
for u in range(N):
    if visited[u] == 1:
        continue
    curr = 1
    next_u = path[u]
    while next_u:
        v = next_u.pop()
        if visited[v] == 1:
            continue
        visited[v] = 1
        curr += 1
        for w in path[v]:
            if visited[w] == 0:
                next_u.add(w)
    ans = max(ans, curr)

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
path = [set() for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1].add(b-1)
    path[b-1].add(a-1)
visited = [1] + [0] * (N-1)

ans = 1
for u in range(N):
    if visited[u] == 1:
        continue
    curr = 1
    next_u = path[u]
    while next_u:
        v = next_u.pop()
        if visited[v] == 1:
            continue
        visited[v] = 1
        curr += 1
        for w in path[v]:
            if visited[w] == 0:
                next_u.add(w)
    ans = max(ans, curr)

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
path = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1] += [b-1]
    path[b-1] += [a-1]
visited = [1] + [0] * (N-1)

ans = 1
for u in range(N):
    if visited[u] == 1:
        continue
    curr = 1
    next_u = path[u]
    while next_u:
        v = next_u.pop()
        if visited[v] == 1:
            continue
        visited[v] = 1
        curr += 1
        for w in path[v]:
            if visited[w] == 0:
                next_u += [w]
    print(u, curr)
    ans = max(ans, curr)

print(ans)

Submission status: Wrong Answer

Solution code:
'''
    	We can show that if u and v belong to the same connected component, then they are friends w/ each other
    	So everyone in a given connected component is friends with one another
    	So everyone in a given connected component must be separated into different groups

    	If we have a CC of with sz nodes in it, then we need at least sz different groups

    	So, the minimum number of groups needed is max sz(CC)
    '''
import sys
sys.setrecursionlimit(4*10**5)

n, m = map(int,input().split())
adj = [[] for u in range(n+1)]
for i in range(m):
  u, v = map(int,input().split())
  adj[u].append(v)
  adj[v].append(u)

  vis = [False for u in range(n+1)]
  def dfs(u):
    if vis[u]:
      return 0
    vis[u] = True

    sz = 1
    for v in adj[u]:
      sz += dfs(v)
      return sz

    CCs = []
    for u in range(1,n+1):
      if not vis[u]:
        CCs.append(dfs(u))

        print(max(CCs))

Submission status: Wrong Answer

Solution code:
from collections import Counter

N ,M =map(int, input().split())
# method1
pair_set = set()
group_list = [i for i in range(N)]
for i in range(M):
    A ,B = map(int, input().split())
    if A > B:
        A, B = B, A
    pair_set.add((A, B))
#print(sorted(pair_set))
for a,b in sorted(pair_set):
    if group_list[b-1] >= group_list[a-1]:
        group_list[b-1] = group_list[a-1]
    else:
        group_list[a-1] = group_list[b-1]
#print(group_list)
group_count = Counter(group_list)
max_count = 0
for c in group_count.values():
    if c > max_count:
        max_count = c
print(max_count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N ,M =map(int, input().split())
# method1
pair_set = set()
group_list = [i for i in range(N)]
for i in range(M):
    A ,B = map(int, input().split())
    if A > B:
        A, B = B, A
    pair_set.add((A, B))
for a,b in sorted(pair_set):
    group_list[b-1] = group_list[a-1]
group_count = Counter(group_list)
max_count = 0
for c in group_count.values():
    if c > max_count:
        max_count = c
print(max_count)

Submission status: Wrong Answer

Solution code:
def main():
  N, M = map(int, input().split())
  
  f_lst = [[] for i in range(N)]
  count = [0] * (N+1)
  
  for _ in range(M):
    A, B = map(int, input().split())
    if not B in f_lst[A-1]:
      f_lst[A-1].append(B)
      f_lst[B-1].append(A)
      count[A] += 1
      count[B] += 1
  print(max(count)+1)
 
main()

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().split()]
A = list(range(N+1))
for _ in range(M):
  a,b = [int(i) for i in input().split()]
  a,b = [max(a,b),min(a,b)]
  A[a] = b
for i in range(N+1):
  n = A[i]
  while n != A[n]:
    n = A[n]
  A[i] = n
L = [0]*(N+1)
for a in A:
  L[a] += 1
print(max(L))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ans = 0
if m == 0:
    print(1)
    exit()
relationships = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
    relationships[i].sort()

relationships.sort()
groups = []
groups.append(set(relationships[0]))
ch = relationships[0][0]
cnt = 0
for i in range(1, m):
    if ch == relationships[i][0]:
        groups[cnt].add(relationships[i][1])
    else:
        for j in range(len(groups)):
            if relationships[i][1] in groups[j]:
                groups[j].add(relationships[i][0])
                ch = relationships[i][0]
                cnt = j
                break
        if ch != relationships[i][0]:
            groups.append(set(relationships[i]))
            ch = relationships[i][0]
            cnt = j + 1
for group in groups:
    ans = max(ans, len(group))

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ans = 0
if m == 0:
    print(n)
    exit()
relationships = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
    relationships[i].sort()

relationships.sort()
groups = []
groups.append(set(relationships[0]))
ch = relationships[0][0]
cnt = 0
for i in range(1, m):
    if ch == relationships[i][0]:
        groups[cnt].add(relationships[i][1])
    else:
        for j in range(len(groups)):
            if relationships[i][1] in groups[j]:
                groups[j].add(relationships[i][0])
                ch = relationships[i][0]
                cnt = j
                break
        if ch != relationships[i][0]:
            groups.append(set(relationships[i]))
            ch = relationships[i][0]
            cnt = j + 1
for group in groups:
    ans = max(ans, len(group))

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

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

A = [0] * n

mamimum = 1

if m != 0:
    B = []
    C = []

    for i in range(m):
        b, c = map(int, input().split())
        B.append(b)
        C.append(c)

    D = zip(B, C)
    D = sorted(D)
    B, C = zip(*D)

    for i, j in zip(B, C):
        i -= 1
        j -= 1
        if A[i] == 0 and A[j] == 0:
            A[i] = mamimum
            A[j] = mamimum
            mamimum += 1
        elif A[i] == 0:
            A[i] = A[j]
        elif A[j] == 0:
            A[j] = A[i]

    D = collections.Counter(A)
    list_D = list(D.values())
    if 0 in A:
        list_D[list(D.keys()).index(0)] = 0
    print(max(list_D))

else:
    print(1)

Submission status: Wrong Answer

Solution code:
import collections

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

A = [0] * n

mamimum = 1

if m != 0:
    B = []
    C = []

    for i in range(m):
        b, c = map(int, input().split())
        B.append(b)
        C.append(c)

    D = zip(B, C)
    D = sorted(D)
    B, C = zip(*D)

    for i, j in zip(B, C):
        i -= 1
        j -= 1
        if A[i] == 0 and A[j] == 0:
            A[i] = mamimum
            A[j] = mamimum
            mamimum += 1
        elif A[i] == 0:
            A[i] = A[j]
        elif A[j] == 0:
            A[j] = A[i]

    D = collections.Counter(A)
    print(max(D.values()))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
import collections

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

A = [0] * n

mamimum = 1

if m != 0:
    B = []
    C = []

    for i in range(m):
        b, c = map(int, input().split())
        B.append(b)
        C.append(c)

    D = zip(B, C)
    D = sorted(D)
    B, C = zip(*D)

    for i, j in zip(B, C):
        i -= 1
        j -= 1
        if A[i] == 0 and A[j] == 0:
            A[i] = mamimum
            A[j] = mamimum
            mamimum += 1
        elif A[i] == 0:
            A[i] = A[j]
        elif A[j] == 0:
            A[j] = A[i]

    D = collections.Counter(A)
    print(max(D.values()))
else:
    print(n)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())
friends = [[] for _ in range(N+1)]
for __ in range(M):
  a, b = map(int, input().split())
  friends[a].append(b)
  friends[b].append(a)
checked = [0 for ___ in range(N+1)]
answer = 0
for i in range(1, N+1):
  friend = deque(friends[i])
  cnt = 0
  while(len(friend) > 0):
    f = friend.popleft()
    if checked[f] != 0:
      continue
    else:
      checked[f] = 1
      cnt += 1
      for ff in friends[f]:
        friend.append(ff)
  answer = max(answer, cnt)
print(answer)

Submission status: Wrong Answer

Solution code:
N,M = tuple(map(int,input().split()))
matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = list(range(N))
# [所属先,[所属メンバー]]
gplist = [[i] for i in range(N)]
def match(ab):
    a,b=ab
    gpa=friendlist[a]
    gpb=friendlist[b]
    mema=gplist[a].copy()
    memb=gplist[b].copy()
    if gpa==gpb:
        return
    else:
        gplist[gpa].extend(memb)
        for i in memb:
            friendlist[i]=gpa
        gplist[b] = [-1]

# print(gplist)
for i in range(M):
    match(matchlist[i])
    # print(gplist)
    # print(friendlist)
print(max([len(item) for item in gplist]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections


n,m = map(int, input().split())
par = [i for i in range(n)]
rank = [0]*n

def find(x):
    if par[x] == x:
        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
    if rank[x] < rank[y]:
        par[x] = y
    if rank[x] > rank[y]:
        par[y] = x
    if rank[x] == rank[y]:
        rank[x] += 1

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

    count = [0]*n
    for p in par:
        count[find(p)] += 1
    print(max(count))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main(N, M, C):
    lst = [n for n in range(N)] # 初期値はすべてがそれぞれ根である状態

    def get_root(x):    # 根を得る関数
        if lst[x] == x: # それ自身が根である場合
            return x
        else:   # 根が別のものである場合
            lst[x] = get_root(lst[x])   # 経路圧縮あり (ある種「メモ再帰化」)
            return lst[x]
            # return get_root(lst[x]) # 経路圧縮なし (わかりやすい，ただの再帰関数) → これだと最後一番大きな集合の大きさを調べることができない．

    def unite(x, y):
        root_x = get_root(x)
        root_y = get_root(y)
        if root_x != root_y:    # 根が違う (=異なる集合) ならば
            lst[root_x] = root_y

    {unite(*c) for c in C}

    print(max(Counter(lst).values()))


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()

    for _ in range(M):
        C.add(tuple(map(lambda x:int(x)-1, input().split())))   # pythonのindexに合わせるために "-1"
    main(N, M, C)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
group = [0] * (n+1)
lst = []
for _ in range(m):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  lst.append((a, b))

lst.sort()
for i in range(m):
  a, b = lst[i]
  if group[a] == 0 and group[b] == 0:
    group[a] = a
    group[b] = a
  else:
    if group[a] == 0:
      group[a] = group[b]
    elif group[b] == 0:
      group[b] = group[a]
    else:
      group[a], group[b] = min(group[a], group[b]), min(group[a], group[b])

cnt = [0] * (n+1)
for j in range(1, n+1):
  cnt[group[j]] += 1
  
print(max(cnt[1:]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
group = [0] * (n+1)
lst = []
for _ in range(m):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  lst.append((a, b))

lst.sort()
for i in range(m):
  a, b = lst[i]
  if group[a] == 0:
    group[a] = a
  group[b] = group[a]

cnt = [0] * (n+1)
for j in range(1, n+1):
  cnt[group[j]] += 1
  
print(max(cnt[1:]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
group = [0] * (n+1)
lst = []
for _ in range(m):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  lst.append((a, b))

lst.sort()
for i in range(m):
  a, b = lst[i]
  if group[a] == 0:
    group[a] = a
  group[b] = group[a]

cnt = [0] * (n+1)
for j in range(1, n+1):
  cnt[group[j]] += 1
  
print(max(cnt))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
group = [0] * (n+1)
lst = []
for _ in range(m):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  lst.append((a, b))

lst.sort()
for i in range(m):
  a, b = lst[i]
  if group[a] == 0:
    group[a] = a
  group[b] = group[a]

group.sort()
cnt = 0
ans = 0
pre = group[1]
for j in range(1, n+1):
  if group[j] == pre:
    cnt += 1
  else:
    ans = max(ans, cnt)
    cnt = 1
  pre = group[j]
ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

lst = [True] * (n+1)
ans = 0
for i in range(1, n+1):
  if lst[i]:
    friends = group[i]
    friends.add(i)
    for friend in group[i]:
      friends = friends | group[friend]
      lst[friend] = False
    cnt = len(friends)
    ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

lst = [True] * (n+1)
ans = 0
for i in range(1, n+1):
  if lst[i]:
    friends = group[i]
    for friend in group[i]:
      friends = friends | group[friend]
      lst[friend] = False
    cnt = len(friends)
    ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
set_array = []
for x in range(0, m):
    ta, tb = map(int, input().split())
    set_array.append({ta, tb})

max_set_len = 2
for i in range(0, m):
    for j in range(i+1, m):
        if set_array[i] & set_array[j]:
            set_array[i] = set_array[i] | set_array[j]
            if len(set_array[i]) > max_set_len:
                max_set_len = len(set_array[i])

print(max_set_len)

Submission status: Wrong Answer

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

# 行先記憶用
rooting = [[] for _ in range(N+1)]

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

# グループの最大人数
max_group_num = 1

# 到達判定フラグ（到達していれば1）
visited = [0 for _ in range(N+1)]

# 幅優先探索
for i in range(1, N+1):
    queue = [i]
    group_num = 1

    while not queue == []:
        h = queue.pop(0)

        if visited[h] == 1:
            break
        else:
            visited[h] = 1
        
        for n in rooting[h]:
            queue.append(n)
            if visited[n] != 1:
                group_num += 1
                visited[n] = 1

    max_group_num = max(max_group_num, group_num)

print(max_group_num)

Submission status: Wrong Answer

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

# 行先記憶用
rooting = [[] for _ in range(N+1)]

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

# グループの最大人数
max_group_num = 1

# 到達判定フラグ（到達していれば1）
visited = [0 for _ in range(N+1)]

# 幅優先探索
for i in range(1, N+1):
    queue = [i]
    group_num = 1

    while not queue == []:
        h = queue.pop(0)

        if visited[h] == 1:
            break
        else:
            visited[h] = 1
        
        for n in rooting[h]:
            if visited[n] != 1:
                queue.append(n)
                group_num += 1
                visited[n] = 1

    max_group_num = max(max_group_num, group_num)

print(max_group_num)

Submission status: Wrong Answer

Solution code:
N,M = tuple(map(int,input().split()))
# matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
# friendlist = [0 for i in range(N)]
gplist = [[-1]]
def match(ab):
    a,b=ab
    igpa = 0
    igpb = 0
    for i,gp in enumerate(gplist):
        if a in gp:
            igpa = i
            if b in gp:
                return
        elif b in gp:
            igpb = i
        if bool(igpa) and bool(igpb):
            break
    if not bool(igpa) and not bool(igpb):
        gplist.append([a,b])
    elif bool(igpa) and not bool(igpb):
        gplist[igpa].append(b)
    elif not bool(igpa) and bool(igpb):
        gplist[igpb].append(a)
    else:
        gplist[igpa].extend(gplist[igpb])
        gplist.remove(gplist[igpb])


print(gplist)
for i in range(M):
    # match(matchlist[i])
    match(tuple(map(lambda x:int(x)-1,input().split())))
    # print(gplist)
print(max([len(item) for item in gplist]))

Submission status: Wrong Answer

Solution code:
N,M = tuple(map(int,input().split()))
matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = [[i] for i in range(N)]

def match(ab):
    a,b=ab
    lsa = friendlist[a].copy()
    lsb = friendlist[b].copy()
    if a in lsb:
        return
    else:
        for ip in lsa:
            friendlist[ip].extend(lsb)
        for ip in lsb:
            friendlist[ip].extend(lsa)

for i in range(M):
    match(matchlist[i])
    print(friendlist)
print(max([len(item) for item in friendlist]))

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

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

ans = 0

uf = UnionFind(n)
for i in range(m):
    friends = list(map(int, input().split()))
    uf.union(friends[0]-1,friends[1]-1)
    if ans < uf.size(friends[1]-1):
        ans = uf.size(friends[1]-1)
print(ans)

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

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

ans = 0

uf = UnionFind(n)
for i in range(m):
    friends = list(map(int, input().split()))
    uf.union(friends[0]-1,friends[1]-1)
    if ans < uf.size(friends[0]-1):
        ans = uf.size(friends[0]-1)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = tuple(map(int,input().split()))
matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = [[i] for i in range(N)]

def match(ab):
    a,b=ab
    lsa = friendlist[a].copy()
    lsb = friendlist[b].copy()
    if a in lsb:
        return
    else:
        friendlist[a].extend(lsb)
        friendlist[b].extend(lsa)

for i in range(M):
    match(matchlist[i])
    # print(friendlist)
print(max([len(item) for item in friendlist]))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

graph = [[] for _ in range(n+1)]

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

dist = [-1] * (n+1)
dist[0] = 0


d = deque()
ans = 0
for j in range(len(dist)):
    if dist[j] != -1:
        continue
    d.append(j)
    cnt = 0
    while d:
        v = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
            cnt = cnt + 1
    ans = max(ans,cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
def find(x):
    if par[x]==x:
        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 0
    if x<y:x,y=y,x    
    par[x]=y
n,m=map(int,input().split())
par=[i for i in range(n+1)]
for _ in range(m):
    i,j=map(int,input().split())
    unite(i,j)
ans=[0]*(n+1)
for i in par:
    ans[i]+=1
print(max(ans))

Submission status: Wrong Answer

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

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 -self.parents[self.find(x)]

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return -self.parents[self.find(x)]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)
    ans = 0
    for i in range(M):
        x, y = map(int, input().split())
        ans = max(uf.union(x,y), ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#ABC177
#D - Friends
 
N,M=map(int,input().split())
 
friends=[[i,[i]] for i in range(N)]

for i in range(M):
  x,y=sorted(map(lambda x :int(x)-1,input().split()))
  a=friends[x][0]
  friends[a][1].extend([friends[y][0]])
  friends[y][0]=x

group=[len(set(i[1])) for i in friends]

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

Submission status: Wrong Answer

Solution code:
#ABC177
#D - Friends
 
N,M=map(int,input().split())
 
friends=[[i,[i]] for i in range(N)]

for i in range(M):
  x,y=sorted(map(lambda x :int(x)-1,input().split()))
  a=friends[x][0]
  friends[a][1].extend([friends[y][0]])
  friends[y][0]=x

group=[len(i[1]) 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())

P=[i for i in range(n)]
R=[0]*n

def find(x):
	if P[x]!=x:
		P[x]=find(P[x])
	return P[x]

def unite(x,y):
	x=find(x)
	y=find(y)
	if x==y:
		return

	if R[x]<R[y]:
		P[x]=y
	else:
		P[y]=x
		if R[x]==R[y]:
			R[x]+=1

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

m,c,p=0,0,-1
for i in sorted(P):
  if p!=i:
    c,p=1,i
  else:
    c+=1
  m=max(m,c)

print(m)

Submission status: Wrong Answer

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

P=[i for i in range(n)]
R=[0]*n

def find(x):
	if P[x]!=x:
		P[x]=find(P[x])
	return P[x]

def unite(x,y):
	x=find(x)
	y=find(y)
	if x==y:
		return

	if R[x]<R[y]:
		P[x]=y
	else:
		P[y]=x
		if R[x]==R[y]:
			R[x]+=1

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

m,c,p=0,0,-1
for i in sorted(P):
  if p!=i:
    m=max(m,c)
    c,p=1,i
  else:
    c+=1

print(max(m,c))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())  # M pieces of information for N people
encountered = []
friends = [['a']]

for _ in range(M):
    a, b = map(int, input().split())
    a_enc = a in encountered
    b_enc = b in encountered

    if [a_enc, b_enc] == [False, False]:
        friends.append([a, b])
        encountered.append([a, b])

    elif [a_enc, b_enc] == [False, True]:
        for i in range(len(friends)):
            if b in friends[i]:
                friends[i].append(a)
                break
        encountered.append(a)

    elif [a_enc, b_enc] == [True, False]:
        for i in range(len(friends)):
            if a in friends[i]:
                friends[i].append(b)
                break
        encountered.append(b)

    else:  # if both has been encountered before
        a_loc, b_loc = 0, 0
        for i in range(len(friends)):
            if a in friends[i]:
                a_loc == i
            if b in friends[i]:
                b_loc == i
            if a_loc != 0 and b_loc != 0:
                break
        if a_loc != b_loc:
            friends[a_loc] += friends[b_loc]
            del friends[b_loc]

print(max(map(len, friends)))