Problem:


Score : 300 points

Problem Statement

There are N cities numbered 1 through N, and M bidirectional roads numbered 1 through M.
Road i connects City A_i and City B_i.

Snuke can perform the following operation zero or more times:

Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.

After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).

What is the minimum number of roads he must build to achieve the goal?

Constraints

2 \leq N \leq 100,000

1 \leq M \leq 100,000

1 \leq A_i < B_i \leq N

No two roads connect the same pair of cities.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

Print the answer.

Sample Input 1

3 1
1 2

Sample Output 1

1

Initially, there are three cities, and there is a road between City 1 and City 2.

Snuke can achieve the goal by building one new road, for example, between City 1 and City 3.
After that,

We can travel between 1 and 2 directly.

We can travel between 1 and 3 directly.

We can travel between 2 and 3 by following both roads (2 - 1 - 3).



Sample input:
3 1
1 2


Sample output:
1

Submission status: Accepted

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

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

        return self.root(rx)

    def is_root(self, x):
        rx = self.r[x]
        return rx < 0

    def unit(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        r = self.r

        if r[x] > r[y]:
            x, y = y, x

        r[x] += r[y]
        r[y] = x

        return True

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

    def debug(self):
        print(self.r)


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

union_find = UnionFind(N)

for _ in range(M):
    A, B = map(int, input().split())
    union_find.unit(A-1, B-1)

count_union = 0
for i in range(N):
    if union_find.is_root(i):
        count_union += 1

print(count_union-1)

Submission status: Accepted

Solution code:
import sys,io,os
I = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
#I = input

n,m = map(int, I().split())
p=[-1]*(n+1)
s=[0]*(n+1)
S=n-1
def t(a):
	b = a
	while p[b] != -1:
		b = p[b]
	while p[a] != -1:
		p[a],a = b,p[a]
	return a
for _ in range(m):
	a,b=map(int, I().split())
	a,b = t(a), t(b)
	if a != b:
		S -= 1
		if s[a] > s[b]:
			a,b = b,a
		p[a] = b
		s[b] += s[a]
print(S)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
        
nn,mm = map(int,input().split());
a = [input().split() for l in range(mm)]
uf = UnionFind(nn)

for ii in range(mm):
    uf.union(int(a[ii][0]), int(a[ii][1]))

b = [0]*nn
for r in range(1,nn+1):
    b[uf.find(r)-1] += 1
 
con = 0
for vv in range(nn):
    if b[vv] != 0:
        con += 1
print(con-1)

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

def main():
    n, m = map(int, input().split())
    u = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        u.union(a - 1, b - 1)
    print(u.group_count() - 1)
    
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


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)

count = 0
for k, v in Counter(uf.parents).items():
    if k < 0:
        count += v

print(count - 1)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input = sys.stdin.readline

N,M = map(int,input().split())
uf = UnionFindVerSize(N)
for i in range(M):
    u,v = map(int,input().split())
    uf.unite(u-1,v-1)

print(uf.calc_group_num()-1)

Submission status: Accepted

Solution code:
class UF:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

tr = UF(n)
for a,b in ab:
  tr.union(a, b)
count = [0]*(n+1)
for i in tr.par:
  count[tr.find(i)] = 1
print(sum(count)-2)

Submission status: Accepted

Solution code:
from collections import deque

R = lambda: map(int, input().split())
n, m = R()
g = [None] + [[] for _ in range(n)]
V = [None] + [False] * n
for _ in range(m):
  u, v = R()
  g[u].append(v)
  g[v].append(u)

q = deque()
r = -1
for u in range(1, n + 1):
  if not V[u]:
    r += 1
    V[u] = True
    q.append(u)
    while q:
      u = q.popleft()
      for v in g[u]:
        if not V[v]:
          V[v] = True
          q.append(v)

print(r)

Submission status: Accepted

Solution code:
import sys


def dfs(v):
    global visited
    visited[v] = True
    for nv in graph[v]:
        if nv in graph[v]:
            if not visited[nv]:
                dfs(nv)


if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    visited = [False]*N
    for _ in range(M):
        A, B = map(lambda x: int(x)-1, input().split())
        graph[A].append(B)
        graph[B].append(A)
    ans = -1
    for v in range(N):
        if not visited[v]:
            dfs(v)
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

par = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

for a, b in edges:
    unite(a, b)
memo = [False for _ in range(n + 1)]
ans = 0
for i in range(1, n + 1):
    r = root(i)
    if memo[r] == False:
        memo[r] = True
        ans += 1

print(ans - 1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
l = []
for i in range(M):
  l.append(list(map(int, input().split())))
  
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans
      
uf = UnionFindVerSize(N+1)
for i in range(M):
  a, b = l[i][0], l[i][1]
  uf.unite(a, b)
  
a = uf.calc_group_num()
print(a-2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        self.d = []
        for _ in range(n):
            self.d.append(-1)
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x

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

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


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)
group = set()
for i in range(N):
    group.add(uf.find(i))

print(len(group)-1)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = list(range(n)) #親
        self.rank = [0] * n #根の深さ

    # xの属する根を求める
    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            # if they have the same parent, no need to union
            return
        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

    # xとyが同じ集合に属するかを判定（同じ根に属するか）
    def same(self, x, y):
        return self.find(x) == self.find(y)


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

for _ in range(M):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = -1
for i in range(N):
    if uf.par[i] == i:
        ans +=1
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 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())
        
a = input().split()
N = int(a[0])
M = int(a[1])
tm = int(0)
tmp = int(0)


k = [input().split() for i in range(M)]

uf = UnionFind(N+1)

for i in range(M):
    tm = int(k[i][0])
    tmp = int(k[i][1])
    uf.union(tm, tmp)
    tm = 0
    tmp = 0

print(int(uf.group_count()) - 2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import networkx as nx

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()

    for i in range(1, N+1):
        G.add_node(i)

    for i in range(M):
        G.add_edge(A[i], B[i])

    if nx.is_connected(G):
        print(0)
    else:
        print(nx.number_connected_components(G)-1)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
# 1 2 3
# a, b, c = LI()


def I(): return int(sys.stdin.buffer.readline())
# a = I()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
# abc def
# a, b = LS()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
# a = S()


def IR(n): return [I() for i in range(n)]
# 2
# 1
# 2
# [1, 2]


def LIR(n): return [LI() for i in range(n)]
# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def SR(n): return [S() for i in range(n)]
# 2
# abc
# def
# [abc, def]


def LSR(n): return [LS() for i in range(n)]
# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def SRL(n): return [list(S()) for i in range(n)]
# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


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 = LI()
uf = UnionFind(n)
for _ in range(m):
    a, b = LI()
    uf.union(a-1, b-1)
print(uf.group_count()-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
cla = [i for i in range(N)]
count = set()
def root(a):
    change = []
    while cla[a] != a:
        change.append(a)
        a = cla[a]
    for i in change:
        cla[i] = a
    return a
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if root(a) != root(b):
        cla[root(b)] = root(a)
for i in range(N):
    count |= {root(i)}
print(len(count) - 1)

Submission status: Accepted

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

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

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

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

		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 abs(self.parents[self.find(x)])
      
      
uf=UnionFind(N)
for i in range(M):
  A,B=map(int,input().split())
  uf.union(A-1,B-1)
  
print(len(uf.parents[uf.parents<0])-1)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.UF = [i for i in range(n)]
    def union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        self.UF[px] = py
    def find(self, x):
        if self.UF[x] == x:
            return x
        self.UF[x] = self.find(self.UF[x])
        return self.UF[x]
 
n,m = [int(x) for x in input().split()]
UF = UnionFind(n)
for _ in range(m):
    a,b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    UF.union(a,b)
 
ANS = []
for i in range(n):
    if UF.find(i) != UF.find(0):
        ANS.append((0,i))
        UF.union(i, 0)
print(len(ANS))

Submission status: Accepted

Solution code:
n, m = map(int, input().split(' '))
cnt = 0
circles = [x for x in range(n)]

def find(x):
  if circles[x] == x:
    return x
  root = find(circles[x])
  circles[x] = root
  return root

for _ in range(m):
  a, b = map(int, input().split(' '))
  if find(a - 1) != find(b - 1):
    circles[find(a - 1)] = find(b - 1)
    
print(sum(1 for i, j in enumerate(circles) if i == j) - 1)

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,b=a-1,b-1
  uf.union(a,b)
print(uf.group_count()-1)

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self, N):
        self.N = N
        self.nodes = [ Node(i) for i in range(N) ]

    def get_root(self, node):
        if node.parent is None:
            return node
        root = self.get_root(node.parent)
        node.parent = root
        return root

    def merge(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)

        if root1.ID == root2.ID:
            return

        root1.parent = root2

    def get_root_count(self):
        count = 0
        for n in self.nodes:
            if n.parent is None:
                count += 1
        return count

class Node:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None

def main():
    N, M = map(int, input().split())
    tree = Tree(N)
    for i in range(M):
        A, B = map(int, input().split())
        A, B = A-1, B-1
        tree.merge(tree.nodes[A], tree.nodes[B])
    print(tree.get_root_count() - 1)


main()

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy

    def same(self,x,y):
        return  self[x] == self[y]

    def find_max(self):
        return max(self.size)

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

uf = UnionFind(N)
merge = uf.merge
same = uf.same

for i in range(M):
    a,b = map(int, input().split())
    merge(a,b)
count = -1
for ind,j in enumerate(uf.root):
    if ind == j:
        count += 1

print(count -1)

Submission status: Accepted

Solution code:
class UnionFind:
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rank = [0]*(n+1)

    # ノードxのrootノードを見つける
    def findRoot(self, x):
        if(self.root[x] < 0): # 根
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.findRoot(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.findRoot(x)
        y = self.findRoot(y)
        # すでに同じ木に属していた場合
        if x == y:
            return 
        # 違う木に属していた場合rankを見てくっつける方を決める
        if self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

    # ノードxが属する木のサイズを返す
    def count(self, x):
        return -self.root[self.findRoot(x)]

n,m = map(int,input().split())
t = UnionFind(n)
for _ in range(m):
    a,b = map(int,input().split())
    t.unite(a,b)

#root要素の数-1本の道を加えることで、すべての要素が連結になる
print(len([a for a in t.root[1::] if a < 0])-1)

Submission status: Accepted

Solution code:
import math

class UnionFind:
    def __init__(self, size):
        self.parent_indexes = [-1] * size
        
    def find(self, n):
        if self.parent_indexes[n] < 0:
            return n
        # 探しているnodeが指し示しているのが現在の親ではない場合、
        # 現在の親に書き換え(メモ化) した上で返す
        self.parent_indexes[n] = self.find(self.parent_indexes[n])
        return self.parent_indexes[n] 
    
    def union(self, n1, n2):
        if self.same_group(n1, n2):
            return False
        
        # サイズの大きい方の集団の親が親であり続ける
        if self.size(n1) >= self.size(n2):
            tmp = self.size(n2)
            self.parent_indexes[self.find(n2)] = self.find(n1)
            self.parent_indexes[self.find(n1)] -= tmp
            return True
        
        # サイズが小さい方の集団の親は親を引退する
        tmp = self.size(n1)
        self.parent_indexes[self.find(n1)] = self.find(n2)
        self.parent_indexes[self.find(n2)] -= tmp
        return True
        
    # その要素が所属する集団の要素数
    def size(self, n):
        return -self.parent_indexes[self.find(n)]
    
    def same_group(self, n1, n2):
        return self.find(n1) == self.find(n2)

n, m = map(lambda x: int(x), input().split())


uf = UnionFind(n)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    uf.union(a-1, b-1)
    
num_parents = 0
    
for p_index in uf.parent_indexes:
    if p_index < 0:
        num_parents += 1
# print(uf.parent_indexes)
print(num_parents - 1)

Submission status: Accepted

Solution code:
# n個のデータを0,...n-1でナンバリング
# 再帰上限に注意
import sys
sys.setrecursionlimit(10**9)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]

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

    def union(self, n, m):
        x = self.find(n)
        y = self.find(m)
        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


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

P = U.parents
ans = 0
for p in P:
    if p < 0:
        ans += 1
print(ans-1)

Submission status: Accepted

Solution code:
def ConectCities():
    from collections import deque
    n, m = map(int, input().split())
    a = [[] for _ in range(n)]
    route = set()
    ans = 0
    q = deque()

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

    for i in range(n):
        if i in route:
            continue
        elif i != 0:
            ans += 1
        route.add(i)
        q.append(i)
        
        while q:
            k = q.pop()
            route.add(k)
            for j in a[k]:
                if j in route:
                    continue
                route.add(j)
                q.append(j)
        if len(route) == n:
            print(ans)
            break

if __name__ == '__main__':
    ConectCities()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100002)

input = lambda : sys.stdin.readline().rstrip()


def main(a_s, b_s, n, m):
    graph = {}
    for node in range(1, n+1):
        graph[node] = []

    for i in range(m):
        a, b = a_s[i], b_s[i]
        graph[a].append(b)
        graph[b].append(a)

    uses = [False] * (n+1)

    def check(node):
        uses[node] = True
        kids = graph[node]
        for kid in kids:
            if not uses[kid]:
                check(kid)

    next_graph_i = 1
    for node in range(1, n+1):
        if uses[node]:
            continue
        graph_i = next_graph_i
        check(node)
        next_graph_i = graph_i + 1

    out = graph_i - 1
    print(out)

if True:
    n, m = map(int, input().split(" "))
    a_s = []
    b_s = []
    for i in range(m):
        a, b = map(int, input().split(" "))
        a_s.append(a)
        b_s.append(b)
else:
    import random
    n = random.randint(2, 100000)
    m = random.randint(1, 100000)
    
    a_s = []
    b_s = []
    for i in range(m):    
        a = random.randint(1, n-1)
        b = random.randint(a+1, n)
        a_s.append(a)
        b_s.append(b)

main(a_s, b_s, n, m)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
nodes = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    nodes[a].append(b)
    nodes[b].append(a)

nodes_flag = [False for _ in range(n)]
count = 0
for i in range(n):
    # print("{}:{}".format(i, nodes_flag))
    if nodes_flag[i] is not True:
        count += 1
        nodes_flag[i] = True
        nodes_list = nodes[i]
        while len(nodes_list):
            new_nodes_list =[]
            for node in nodes_list:
                if nodes_flag[node]:
                    continue
                nodes_flag[node] = True
                for next_node in nodes[node]:
                    new_nodes_list.append(next_node)
            nodes_list = new_nodes_list
print(count-1)