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: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections
import itertools
import operator

class UnionFind:
  def __init__(self, elems=None):
    class KeyDict(dict):
      def __missing__(self, key):
        self[key] = key
        return key

    self.parent = KeyDict()
    self.rank = collections.defaultdict(int)
    self.size_ = collections.defaultdict(lambda: 1)

    if elems is not None:
      for elem in elems:
        _, _, _ = self.parent[elem], self.rank[elem], self.size_[elem]

  def find(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find(self.parent[x])
      return self.parent[x]

  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.parent[x] = y
      self.size_[y] += self.size_[x]
    else:
      self.parent[y] = x
      self.size_[x] += self.size_[y]
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1

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

  def grouper(self):
    roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
    root = operator.itemgetter(1)
    for _, group in itertools.groupby(sorted(roots, key=root), root):
      yield [x for x, _ in group]

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


n,m = na()
g = UnionFind()
ans = 0

for i in range(m):
    a,b = na()
    g.unite(a,b)

a = [len(i) for i in list(g.grouper())]

print(max(a))

Submission status: Runtime Error

Solution code:
import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

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

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

def main():
    N, M = mi()
    A, B = i2(M)
    if M == 0:
        print(1)
        return

    uf = Uf(N)
    for i in range(M):
        uf.unite(A[i]-1, B[i]-1)

    print(max(uf.count(i) for i in range(N)))
    


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, m = map(int, input().split())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
size = [1 for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if not same(a - 1, b - 1):
        unite(a - 1, b - 1)
x = [0] * n
ans = 0
for i in range(n):
    j = get_root(i)
    x[j] += 1
    ans = max(ans, x[j])
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math
from  itertools import accumulate

def get_int():return int(stdin.readline().strip())
def get_tuple():return map(int, stdin.readline().split())
def get_list():return list(map(int, stdin.readline().split()))


# Python program to print connected
# components in an undirected graph
class Graph:

    # init function to declare class variables
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]

    def DFSUtil(self, temp, v, visited):

        # Mark the current vertex as visited
        visited[v] = True

        # Store the vertex to list
        temp.append(v)

        # Repeat for all vertices adjacent
        # to this vertex v
        for i in self.adj[v]:
            if visited[i] == False:
                # Update the list
                temp = self.DFSUtil(temp, i, visited)
        return temp

    # method to add an undirected edge
    def addEdge(self, v, w):
        self.adj[v].append(w)
        self.adj[w].append(v)

    # Method to retrieve connected components
    # in an undirected graph
    def connectedComponents(self):
        visited = []
        cc = []
        for i in range(self.V):
            visited.append(False)
        for v in range(self.V):
            if visited[v] == False:
                temp = []
                cc.append(len(self.DFSUtil(temp, v, visited)))
        return cc

    # Driver Code


n,m = get_tuple()
g = Graph(n)
for _ in range(m):
    a,b = get_tuple()
    g.addEdge(a-1,b-1)
cc = g.connectedComponents()
print(max(cc))

Submission status: Runtime Error

Solution code:
class UF:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self,n):
        if self.parent[n] == n :
            return n
        self.parent[n] = self.find(self.parent[n])
        return self.parent[n]

    def union(self, i,j ):
        self.parent[self.find(i)] = self.find(j)


N, M = map(int, input().split(" "))
uf = UF(N)
for _ in range(M):
    i,j = map(lambda x: int(x)-1,input().split(" "))
    uf.union(i,j)

from collections import Counter
arr = []
for i in range(N): 
    arr.append(uf.find(i))

print(Counter(arr).most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

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

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

def main():
    N, M = mi()
    A, B = i2(M)

    uf = Uf(N)

    for i in range(M):
        uf.unite(A[i]-1, B[i]-1)

    print(max(uf.count(i) for i in range(N)))
    


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
edges = defaultdict(set)

for _ in range(M):
    a, b = map(lambda x:int(x)-1, input().split())
    edges[a].add(b)
    edges[b].add(a)

ans = 0
visited = [False] * N

def dfs(i):
    if visited[i]:
        return 0
    ans = 1
    visited[i] = True
    for dest in edges[i]:
        ans += dfs(dest)
    return ans

for i in range(N):
    ans = max(ans, dfs(i))
print(ans)

Submission status: Runtime Error

Solution code:
import collections
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


G = unionFind(N)

for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)
C = collections.Counter(G.parent).most_common()

print(C[0][1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
f = [i for i in range(n + 1)]
def getF(u):
    if f[f[u]] == f[u]:
        return f[u]
    f[u] = getF(f[u])
    return f[u]
def uniF(u, v):
    u = getF(u)
    v = getF(v)
    if u != v:
        f[u] = v
for i in range(m):
    u, v = map(int, input().split())
    uniF(u, v)
c = [0] * (n + 1)
for i in range(1, n + 1):
    c[getF(i)] += 1
print(max(c))

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        # 親の名(いない場合はNone)
        self.parent = [None] * n
        # 子の数
        self.count = [0] * n

    def root(self, x):
        # xの根を返す
        if self.parent[x] is None:
            return x
        else:
            return self.root(self.parent[x])

    def union(self, x, y):
        # xとyをまとめる
        x0 = self.root(x)
        y0 = self.root(y)
        if x0 == y0:
            return
        if x0 > y0:
            x0, y0 = y0, x0
        self.parent[y0] = x0
        self.count[x0] += self.count[y0] + 1

    def size(self, x):
        # xの属する木の大きさ
        return self.count[self.root(x)] + 1

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


n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a - 1, b - 1)
maxSize = 0
for i in range(n):
    maxSize = max(maxSize, uf.size(i))
print(maxSize)