Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Accepted

Solution code:
import os
import heapq
import sys,threading
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase

sys.setrecursionlimit(10 ** 5)
threading.stack_size(2**27)


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def inpt():
    return [int(k) for k in input().split()]

global ct

def bfs(d,visited,s):
    global ct
    q=deque()
    q.append(s)
    visited[s]=True
    while(q):
        x=q.popleft()
        ct+=1
        for i in d[x]:
            if(not visited[i]):
                visited[i]=True
                q.append(i)
def main():
    n,m=inpt()
    st=set()
    d=defaultdict(list)
    for _ in range(m):
        a,b=inpt()
        if((min(a,b),max(a,b)) not in st):
            st.add((min(a,b),max(a,b)))
            d[a].append(b)
            d[b].append(a)

    visited=[False]*(n+1)
    ans=0
    for i in range(1,n+1):
        global ct
        ct=0
        if(not visited[i]):
            bfs(d,visited,i)
            ans=max(ans,ct)
    print(ans)







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

if __name__ == "__main__":
    main()
    #threading.Thread(target=main).start()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
K = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    K[A].append(B)
    K[B].append(A)
used = [0]*N
ans = 0
for i in range(N):
    c = 0
    if used[i] == 0:
        P = deque([i])
        used[i] = 1
        while P:
            c += 1
            a = P.popleft()
            for j in K[a]:
                if used[j] == 0:
                    used[j] = 1
                    P.append(j)
    ans = max(c, ans)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
seen = [False]*(n)
tmp = [-1]*n
from collections import deque
for i in range(n):
    q = deque([])
    if not seen[i]:
        q.append((i,i))
        tmp[i] = i
        while q:
            u,cnt = q.popleft()
            seen[u] = True
            tmp[u] = cnt
            for v in g[u]:
                if not seen[v]:
                    seen[v] = True
                    tmp[i] = cnt
                    q.append((v,cnt))

from collections import Counter
counter = Counter(tmp)

ans = sorted(counter.values())
print(ans[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.buffer.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

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

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

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

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

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

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

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

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

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

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

for i in range(M):
    A, B = map(int,input().split())
    uf.union(A-1,B-1)

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

Submission status: Accepted

Solution code:
import os
import heapq
import sys,threading
import math
import bisect
import operator
from collections import defaultdict
sys.setrecursionlimit(10**6)
threading.stack_size(2**27)
from io import BytesIO, IOBase
def gcd(a,b):
    if b==0:

        return a
    else:
        return gcd(b,a%b)
def power(x, p,m):
    res = 1
    while p:
        if p & 1:
            res = (res * x) % m
        x = (x * x) % m
        p >>= 1
    return res
def inar():
    return [int(k) for k in input().split()]
size=0
def lcm(num1,num2):
    return (num1*num2)//gcd(num1,num2)
def dfs(node,visited,adj):
    global size
    visited[node]=1
    size+=1
    for child in adj[node]:
        if not visited[child]:
            dfs(child,visited,adj)

def main():
    #t=int(input())
    t=1
    for _ in range(t):
        n,m=inar()
        visited=[0]*(n+1)
        adj=defaultdict(list)
        for i in range(m):
            u,v=inar()
            adj[u].append(v)
            adj[v].append(u)
        global size
        ans=1
        for i in range(1,n+1):
            if visited[i]==0:
                size=0
                dfs(i,visited,adj)
                ans=max(ans,size)
        print(ans)






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

if __name__ == "__main__":
    #main()
    threading.Thread(target=main).start()

Submission status: Accepted

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

par = [-1]*n

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

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

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

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

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

mx=0
for i in par:
    if i<0:
        mx=max(mx, -i)

print(mx)

Submission status: Accepted

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

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1; b-= 1
    g[a].append(b)
    g[b].append(a)
friends = [0 for _ in range(n)]

def dfs(v):
    global n
    friends[v] = n
    n += 1
    for next_v in g[v]:
        if friends[next_v] == 0:
            dfs(next_v)
    
for i in range(n):
    if friends[i] == 0:
        n = 1
        dfs(i)
print(max(friends))

Submission status: Accepted

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

    par = [x for x 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
        else:
            par[y] = x
            if rank[x] == rank[y]: rank[x] += 1

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

    for i in range(n):
        _ = find(i)

    from collections import Counter
    ans = Counter(par).most_common()[0][1]
    print(ans)

if __name__ == '__main__':
    abc177_d()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main 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 same(self, x, y):
        return self.find(x) == self.find(y)

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

N, M = getNM()
U = UnionFind(N)
for i in range(M):
    a, b = getNM()
    a -= 1
    b -= 1
    U.union(a, b)

ans = 1
for i in range(N):
    ans = max(ans, U.size(i))
print(ans)

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, size):
        # -nが木のroot
        # 親ノードの位置を格納
        self.table = [-1 for i in range(size)]

    def _find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def get_ntree(self):
        res = 0
        for c in self.table:
            if c < 0:
                res += 1
        return res

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

    def get_nclass(self):
        done = []
        for x in range(len(self.table)):
            if x in done:
                continue
            while self.table[x] >= 0:
                done.append(x)
                x = self.table[x]

    def get_nodenum(self):
        res = []
        for t in self.table:
            if t < 0:
                res.append(-t)

        return res


def ij_to_n(i, j, W):
    return i*W+j


def n_to_ij(n, W):
    return (n//W, n % W)


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


if __name__ == '__main__':
    a, b = acinput()

    uf = UnionFind(a)
    for i in range(b):
        s, t = acinput()
        uf.union(s-1, t-1)

    print(-min(uf.table))

Submission status: Accepted

Solution code:
import sys

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    grpsizes = [0]
    visited = set()
    for i in range(n):
        if not i in visited:
            stack = [i]
            while stack:
                el = stack.pop()
                if not el in visited:
                    visited.add(el)
                    grpsizes[-1] += 1
                    stack.extend(adj[el])
            grpsizes.append(0)
    print(max(grpsizes))
    return





n, m = RA()
adj = [[] for _ in range(n)]
for i in range(m):
    u, v = RA()
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)
adj = [list(set(a)) for a in adj]
solve()

Submission status: Accepted

Solution code:
from collections import deque
N,M = [int(hoge) for hoge in input().split()]
Friend = [[] for _ in range(N)]
for m in range(M):
    A,B = [int(hoge)-1 for hoge in input().split()]
    Friend[A].append(B)
    Friend[B].append(A)
Root = [-1]*N
Youso = []
curnum = 0
for n in range(N):
    Y = 0
    if Root[n] == -1:
        Root[n] = curnum
        Y += 1
        queue = deque()#pop,appendleft
        queue.append(n)
        while queue:
            curpos = queue.pop()
            for tsugi in Friend[curpos]:
                if Root[tsugi] == -1:
                    queue.appendleft(tsugi)
                    Root[tsugi] = curnum
                    Y += 1
        Youso.append(Y)
print(max(Youso))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N,M = map(int,sys.stdin.readline().split())
ab = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)) # multi line with multi param

parents = list(range(N))
def find(x):
  while parents[x] != x:
    x = parents[x]
    parents[x] = parents[parents[x]]
  return x
def union(s,t):
  sp = find(s)
  tp = find(t)
  if sp == tp:
    pass
  elif sp < tp:
    parents[sp] = tp
  else:
    parents[tp] = sp

for a,b in ab:
    union(a-1,b-1)
import collections
d = collections.defaultdict(int)
m = 0
for i in range(N):
    x = find(i)
    d[x] += 1
    m = max(m,d[x])
print(m)

Submission status: Accepted

Solution code:
class UnionFind: 
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
        self.sizes = [1] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        sx, sy = self.sizes[x], self.sizes[y]
        if x == y: return (0, 0)
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
            self.sizes[y] += sx
        else:
            self.pars[y] = x
            self.sizes[x] += sy
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
        return (sx, sy)
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)
    def getSize(self, x):
        return self.sizes[self.getRoot(x)]

import sys
input = sys.stdin.buffer.readline
n, m = map(int,input().split())

uf = UnionFind(n)
e = [[] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    if not b in e[a]:
        uf.merge(a,b)

print(max(uf.sizes))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  uf.union(a, b)

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

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

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

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

N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    uf.union(a, b)

ans = 0
for x in uf.roots():
    ans = max(ans, uf.size(x))

print(ans)