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:
def zero_origin(s: str):
  return int(s) - 1


class UnionFindTree:
  """Union Find Tree for disjoint-set data structure.

  Args:
    n (int): number of the vertices.
  """
  def __init__(self, n: int):
    self.parent = list(range(n))
    self.rank = [0] * n
    self.size = [1] * n

  def find(self, i: int) -> int:
    if self.parent[i] != i:
      self.parent[i] = self.find(self.parent[i])
    return self.parent[i]

  def unite(self, i: int, j: int):
    ri = self.find(i)
    rj = self.find(j)
    if ri != rj:
      if self.rank[ri] < self.rank[rj]:
        self.parent[ri] = rj
        self.size[rj] += self.size[ri]
      else:
        self.parent[rj] = ri
        self.size[ri] += self.size[rj]
        if self.rank[ri] == self.rank[rj]:
          self.rank[ri] += 1

  def is_same(self, i: int, j: int) -> bool:
    return self.find(i) == self.find(j)


n, m = map(int, input().split())
uft = UnionFindTree(n)
for _ in range(m):
  a, b = map(zero_origin, input().split())
  uft.unite(a, b)
print(max(uft.size))

Submission status: Accepted

Solution code:
from collections import Counter
n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        # 要素が根の場合、-(そのグループの要素数)を格納
        self.parents = [-1] * n
        
    # 要素xが属するグループの根を返す    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    # 要素xが属するグループと要素yが属するグループとを併合する
    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
    
    # 要素xが属するグループのサイズ(要素数)を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x, yが同じグループに属すかどうか返す
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要素xが属するグループに属する要素をリストで返す
    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()}
    
    # printでの表示用, ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

tree = UnionFind(n)
for a, b in ab:
    a,b = a-1, b-1
    if not tree.same(a, b):
        tree.union(a, b)
ans = float("-inf")
for i in range(n):
    ans = max(ans, tree.size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())


class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.r = [1]*n

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_members(self, x):
        return -self.p[self.find(x)]


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

print(max(map(lambda i: uf.count_members(i), range(n))))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
friend=[[] for _ in range(N)]
for i in range(M):
    A,B=map(int,input().split())
    friend[A-1].append(B-1)
    friend[B-1].append(A-1)
ans=0
ischecked=[0]*N
for i in range(N):
    if ischecked[i]==1:
        continue
    group=1
    ischecked[i]=1
    ship=friend[i]
    while ship:
        nex=ship.pop()
        if ischecked[nex]==1:
            continue
        ischecked[nex]=1
        group+=1
        ship.extend(friend[nex])
    ans=max(ans,group)
print(ans)

Submission status: Accepted

Solution code:
class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n
    
    def find_root(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find_root(self.parents[x])
            return self.parents[x]
    def make_union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        
        if x == y : return
        self.size[x] += self.size[y]
        self.parents[y] = x

def main():
    n, m = map(int, input().split())
    uf = UnionFindPathCompression(n)
    for _ in range(m):
        a, b = map(int, input().split())
        uf.make_union(a - 1, b - 1)
    
    ans = max(uf.size)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())


class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.r = [1]*n

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_members(self, x):
        return -self.p[self.find(x)]


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

ans = 0
for i in range(n):
    x = uf.count_members(i)
    if ans < x:
        ans = x
print(ans)

Submission status: Accepted

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

  def get_root(self, i):
    if self.parent[i] < 0:
      return i
    else:
      self.parent[i] = self.get_root(self.parent[i])
      return self.parent[i]
    #while self.parent[i] != -1:
    #  i = self.parent[i]
    #return i

  def is_same_tree(self, i, j):
    return self.get_root(i) == self.get_root(j)

  def merge(self, i, j):
    i = self.get_root(i)
    j = self.get_root(j)
    if i == j:
      return

    if self.rank[i] > self.rank[j]:
      self.parent[j] = i
      self.rank[i] = max(self.rank[i], self.rank[j] + 1)
      self.count[i] += self.count[j]
    else:
      self.parent[i] = j
      self.rank[j] = max(self.rank[j], self.rank[i] + 1)
      self.count[j] += self.count[i]


n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = [int(i) - 1 for i in input().split()]
  uf.merge(a, b)
print(max(uf.count))

Submission status: Accepted

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

  def root(self,k):
    if self.par[k] < 0:
      return k
    self.par[k] = self.root(self.par[k])
    return self.par[k]

  def size(self,k):
    k = self.root(k)
    return -self.par[k]

  def unite(self,u,v):
    u = self.root(u)
    v = self.root(v)
    if u==v:
      return
    if self.size(u)<self.size(v):
      u,v = v,u
    self.par[u] += self.par[v]
    self.par[v] = u

def main():
  n,m = map(int,input().split())
  uni = union_find(n+1)
  for _ in range(m):
    ai,bi = map(int,input().split())
    uni.unite(ai,bi)
  ans = max(uni.size(v)for v in range(1,n+1))
  print(ans)

main()

Submission status: Accepted

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

N,Q = 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)
for _ in range(Q):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  uf.union(a,b)
from collections import Counter
a=[-1]*N
for i in range(N):
  a[i]=uf.find(i)
ca=Counter(a)
ans=0
for c in ca.values():
  ans=max(ans,c)
print(ans)

Submission status: Accepted

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

N,Q = map(int,input().split())
class UF():
  def __init__(self,par,rank):
    self.par = par
    self.rank = rank
  def find(self,x):
      if self.par[x] == x:
          return x
      else:
          self.par[x] = self.find(self.par[x]) #経路圧縮
          return self.par[x]
  def same(self,x,y):
      return self.find(x) == self.find(y)
  def unite(self,x,y):
      x = self.find(x)
      y = self.find(y)
      if x == y:
          return 0
      if self.rank[x] < self.rank[y]:
          self.par[x] = y
      else:
          self.par[y] = x
          if self.rank[x]==self.rank[y]:self.rank[x]+=1
uf=UF([i for i in range(N)],[0]*(N+1))
for _ in range(Q):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  uf.unite(a,b)
from collections import Counter
a=[-1]*N
for i in range(N):
  a[i]=uf.find(i)
ca=Counter(a)
ans=0
for c in ca.values():
  ans=max(ans,c)
print(ans)

Submission status: Accepted

Solution code:
import collections
def BFS(graph,start,reached):
    res = 0
    next = []
    if reached[start] == 1:
        return res
    reached[start] = 1
    res += 1
    next += list(graph[start])
    while len(next):
        tmp = next.pop()
        if reached[tmp] == 1:
            continue
        res += 1
        reached[tmp] = 1
        next += list(graph[tmp])
    return res

[n,m] = [int(i) for i in input().split()]
dic = collections.defaultdict(set)
ls = [0] * n
for i in range(m):
    [a,b] = [int(j)-1 for j in input().split()]
    dic[a].add(b)
    dic[b].add(a)
ans = 0
for i in range(n):
    ans = max(ans,BFS(dic,i,ls))
print(ans)

Submission status: Accepted

Solution code:
# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

# from collections import defaultdict
# d = defaultdict(set)

# for i in range(M):
#     a, b = [int(x) for x in input().split(' ')]
#     d[a].add(b)
#     d[b].add(a)

class UF:
    def __init__(self):
        self.r = [-1] * N

    def root(self, i):
        r = self.r
        if r[i] < 0:
            return i
        else:
            r[i] = self.root(r[i])
            return r[i]

    def union(self, i, j):
        i -= 1
        j -= 1
        ri = self.root(i)
        rj = self.root(j)
        if ri == rj:
            return
        else:
            if not self.r[ri] < self.r[rj]:
                ri, rj = rj, ri
            self.r[ri] += self.r[rj]
            self.r[rj] = ri
            return

    def max_size(self):
        return -min(self.r)

uf = UF()
for i in range(M):
    uf.union(*[int(x) for x in input().split(' ')])
print(uf.max_size())

Submission status: Accepted

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

  def get_root(self, i):
    while self.parent[i] != -1:
      i = self.parent[i]
    return i

  def is_same_tree(self, i, j):
    return self.get_root(i) == self.get_root(j)

  def merge(self, i, j):
    i = self.get_root(i)
    j = self.get_root(j)
    if i == j:
      return

    if self.rank[i] > self.rank[j]:
      self.parent[j] = i
      self.rank[i] = max(self.rank[i], self.rank[j] + 1)
      self.count[i] += self.count[j]
    else:
      self.parent[i] = j
      self.rank[j] = max(self.rank[j], self.rank[i] + 1)
      self.count[j] += self.count[i]


n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = [int(i) - 1 for i in input().split()]
  uf.merge(a, b)
print(max(uf.count))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.rank = [1] * n
        self.count = [1] * n
 
    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i
 
    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)
 
    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return
 
        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
            self.count[i] += self.count[j]
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)
            self.count[j] += self.count[i]
n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = [int(i) - 1 for i in input().split()]
  uf.merge(a, b)
print(max(uf.count))

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


import sys
sys.setrecursionlimit(10**7)

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:
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)]


if __name__ == "__main__":
    N, M = map(int, input().split()) 
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)

Submission status: Accepted

Solution code:
import sys

# Union Find
def find(x):
    if par[x] < 0:
        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 False
    else:
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


if __name__ == "__main__":
    input = sys.stdin.readline
    n, m = map(int, input().split())
    par = [-1] * n
    s = set()
    for _ in range(m):
        a, b = map(int, input().split())
        if a > b:
            a, b = b, a
        s.add((a, b))

    for x, y in s:
        unite(x - 1, y - 1)

    print(-min(par))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
li=[-1]*n

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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        li[x] += li[y]
        li[y] = 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
    unite(a, b)

ans=0
for i in range(n):
    ans = max(ans,-li[i])

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]

class UnionFind:
    # まずは最初の状態を作る
    def __init__(self, N):
        # 最初はみんなバラバラ
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0

    # そのノードの根を返す過程で,集合の要素を根に直接つなぎかえる(木の最適化)
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]

    # aとbの根が同じ,つまり同じ連結成分内かどうかを返す
    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    # 連結成分同士を効率的に(rankが大きい方を動かさずにrankが小さい方をくっつける)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        # a, bが同じグループ内にいたから何もしない
        if ra == rb: return
        # 異なるグループにいた場合
        # 短い方をくっつける
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

# friendsは友達の数を保持する
uf = UnionFind(n)
for a, b in ab:
    a, b = a-1, b-1
    # aとbが同連結成分内であれば何もする必要がない
    if uf.is_same(a, b): continue
    # 異なれば結合
    uf.unite(a, b)
# 木の高さの最適化
for i in range(n):
    uf.root(i)
tmp = sorted(Counter(uf.parent).items(), key=lambda x:x[1])
print(tmp[-1][1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

class Union_Find():
    def __init__(self, n):
        """
        要素数n
        """
        self.n = n
        self.par = [-1] * n

    def find(self, x):
        """
        要素xが属するグループの根を返す
        return int
        """
        if self.par[x] < 0:
            return x

        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        要素xが属するグループと要素yが属するグループを併合する
        return null
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        """
        要素xが属するグループの要素数を取得する
        return int
        """
        return - self.par[self.find(x)]
        
    def same(self, x, y):
        """
        要素xと要素yが同じグループに属するかどうかを返す
        return bool
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        要素xが属するグループに属する要素を返す
        return array
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        すべての根の要素を返す
        return array
        """
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        """
        グループ数を返す
        return int
        """
        return len(self.roots())

    def all_group_members(self):
        """
        全てのグループに対してそれぞれ属する要素を返す
        return dict[array]
        """
        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 = Union_Find(N)

for a, b in AB:
    UF.union(a-1, b-1)

ans = 0

for i in UF.roots():
    ans = max(ans, UF.size(i))

print(ans)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)
        self.sizes = [1] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w=1):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.sizes[ry] += self.size(rx)
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.sizes[rx] += self.size(ry)
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

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

uf=WeightedUnionFind(n)
for a,b in ab:
    uf.union(a,b)

# print(uf.par)
dic={}
for i in range(n):
    pa=uf.find(i+1)
    if pa in dic:
        dic[pa]+=1
    else:
        dic[pa]=1

ans=0
for i in dic.values():
    ans=max(ans,i)
print(ans)

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):

        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 

        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y

            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def Output(self):
        return [i for i in self.root if i < 0]

uf = UnionFind(n)
for i in ab:
    uf.Unite(i[0],i[1])

a = [-1 * i for i in uf.Output()]
del a[0]
print(max(a))

Submission status: Accepted

Solution code:
# Union Find
def find(x):
    if par[x] < 0:
        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 False
    else:
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


import sys

input = sys.stdin.readline
n, m = map(int, input().split())
par = [-1] * n
a = set()
for _ in range(m):
    ab = sorted(map(int, input().split()))
    a.add((ab[0], ab[1]))

for x, y in a:
    unite(x - 1, y - 1)

print(-min(par))

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())
union = UnionFind(N)

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

print(-min(union.parents))

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
l = [[] for i in range(n)]
union = []
vis = [-1]*n
ans = 0

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

q = deque()

for i in range(n):
    temp = []
    q.append(i)
    while q:
        a = q.popleft()
        if vis[a] == -1:
            vis[a] = 0
            temp.append(a)
            for j in l[a]:
                q.append(j)
    if len(temp) > 0:
        union.append(temp)


for i in union:
    ans = max(ans, len(i))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().strip().split())
l=list()
dp=[list() for _ in range(N)]
id=[-1 for _ in range(N)] #友人グループid 友人のいない者に-1をつける
for _ in range(M):
    a,b=map(int,input().strip().split())
    l.append((a,b))
    dp[a-1].append(b)
    dp[b-1].append(a)
    id[a-1]=0
    id[b-1]=0

i=1
c=[]
for n in range(1,N+1):
    cnt=0
    if id[n-1]==0:
        q=deque([n])
        while q:
            tmp=q.popleft()
            cnt+=1
            id[tmp-1]=i
            for e in dp[tmp-1]:
                if id[e-1]==0:
                    id[e-1]=i
                    q.append(e)
                else:
                    continue
        i+=1
        c.append(cnt)
    else:
        continue
if c:
    print(max(c))
else:
    print(1)

Submission status: Accepted

Solution code:
import queue

class graph:
    def __init__(self, n):
        self.node = [[] for _ in range(n)]
        self.unexplored = [True for _ in range(n)]
        self.link = []
    
    def unit(self, a, b):
        self.node[a].append(b)
        self.node[b].append(a)
    
    def get_node(self):
        return self.node

    def bfs(self, start, idx):
        self.unexplored[start] = False
        self.link[idx].append(start)
        d = queue.deque()
        d.extend(self.node[start])
        while d:
            vis = d.popleft()
            if self.unexplored[vis]:
                self.link[idx].append(vis)
                self.unexplored[vis] = False
                d.extend(self.node[vis])
    
    def split_link(self):
        idx = 0
        for i in range(len(self.node)):
            if self.unexplored[i]:
                self.link.append([])
                self.bfs(i, idx)
                idx += 1

    def get_linklen(self):
        return [len(x) for x in self.link]

n, m = map(int, input().split())
g = graph(n)
for _ in range(m):
    a, b = map(int, input().split())
    g.unit(a-1, b-1)

g.split_link()
print(max(g.get_linklen()))

Submission status: Accepted

Solution code:
# union-find を使う

# unionするクエリが飛んでくる(クエリ:要求)
# find(どのグループ,集合かわかるようにする)
# findはある要素とある要素が同じグループに属するか,そのグループのサイズはどうか
# この二つを処理する

# 計算量 O(log N) か 工夫すると O(a(N)):アッカーマン計算量の逆関数... ならし計算量

##木構造を作っていく. グループのidはnodeのidにする. findするときは根の番号に辿るようにする

## 計算量を落とす.
### 木がどんどん深くなると処理が長くなる.

## 1. くっつける先を根に向かうようにする, グループとグループは根から根に繋げるようにする
## 小さい方を大きい方にくっつける
## -> 一回あたりO(log(N))
### 高さが高々 log(N)にしかならないから
#### 根から辿ると,一個辿ると頂点の個数が半分以下になっていくから
##### 証明できる: 辺が張られた後は そのグループはいじられない
##### さらに,最初につけたときに既に 残りのグループの方が大きいため

## 2. 経路縮約的な考え
# 計算結果をメモしておく
# 一回計算したところは直接つなぐ　-> メモ化で　ならしlog(N)

##3. 両方を採用すると ならし　アッカーマン関数の逆関数



##実装の工夫

# 根にマイナスのサイズを持つようにする。
# 葉には親のidを持つようにする
# メモ化するためにd[x]を親のfindと一致させるようにする

# MSTを考えてuniteでくっつけられるかどうかを考える

class UnionFind():
    def __init__(self, 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 main():
    n,m = map(int,input().split())
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        uf.union(a-1,b-1)
    
    ans = 1
    for i in range(n):
        ans = max(ans, uf.size(i))
    print(ans)

if __name__ == "__main__":
    main()