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, n: int) -> None:
        self.forest = [-1] * n

    def union(self, x: int, y: int) -> None:
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.forest[x] > self.forest[y]:
            x,y = y,x
        self.forest[x] += self.forest[y]
        self.forest[y] = x
        return

    def findRoot(self, x: int) -> int:
        if self.forest[x] < 0:
            return x
        else:
            self.forest[x] = self.findRoot(self.forest[x])
            return self.forest[x]

    def issame(self, x: int, y: int) -> bool:
        return self.findRoot(x) == self.findRoot(y)

    def size(self,x: int) -> int:
        return -self.forest[self.findRoot(x)]


n,m = map(int,input().split())
uf = UnionFind(n)
s = set()
for i in range(m):
    ai,bi = map(int,input().split())
    uf.union(ai-1,bi-1)

for i in range(n):
    s.add(uf.findRoot(i))
print(len(s)-1)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
A = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  A[a-1].append(b - 1)
  A[b-1].append(a - 1)
B = [0 for i in range(N)]
cnt = 0
for i in range(N):
  if B[i] == 0:
    cnt += 1
    B[i] = cnt
    D = deque([i])
    while len(D) > 0:
      d = D.pop()
      for j in A[d]:
        if B[j] == 0:
          B[j] = cnt
          D.append(j)
print(cnt - 1)

Submission status: Accepted

Solution code:
class uf():


    def __init__(self,n):
        self.size=n
        self.parents=list(range(n))


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


    def union(self,a,b):
        x=self.find(a)
        y=self.find(b)
        if x==y:
            return
        if x>y:
            x,y=y,x
        self.parents[y]=x


    def roots(self):
        s=0
        for c in range(self.size):
            if self.find(c)==c:
                s+=1
        return s-1


n,m=map(int,input().split())
city=uf(n)
for c in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    city.union(a,b)
print(city.roots())

Submission status: Accepted

Solution code:
from collections import Counter
n, m = map(int, input().split())
group = [None for _ in range(n)]
connected = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    connected[a].append(b)
    connected[b].append(a)
# print(connected)
for i in range(n):
    if group[i] is not None: continue
    newly_visited = [i]
    group[i] = i
    while len(newly_visited) > 0:
        new = newly_visited.pop()
        for j in connected[new]:
            if group[j] is not None: continue
            group[j] = i
            newly_visited.append(j)
# print(Counter(group))
print(len(Counter(group)) - 1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
pair = [i for i in range(n + 1)]
def find(x):
    if pair[x] == x:
        return x
    else:
        pair[x] = find(pair[x]) 
        return pair[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    pair[x] = y
    
for i in range(m):
    a, b = map(int, input().split())
    unite(a,b)


ans = 0
for i, k in enumerate(pair[1:], 1):
    if i == k:
        ans += 1
    
print(ans - 1)

Submission status: Accepted

Solution code:
import sys
r=sys.stdin.readline
N,M=map(int,r().split())
city=[[] for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,r().split())
    city[a].append(b)
    city[b].append(a)
check=[True]+[False]*(N)
def dfs(v):
    stack=[v]
    while stack:
        cur=stack.pop()
        check[cur]=True
        for v in city[cur]:
            if not check[v]:
                stack.append(v)
cnt=0
for i in range(1,N+1):
    if not check[i]:
        dfs(i)
        cnt+=1
print(cnt-1)

Submission status: Accepted

Solution code:
#UnionFind
#新しくUnion型みたいな箱を作って使っていると思うと分かりやすい
#最初に箱と要素を用意しておいて、箱同士をつなげてくれている
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):#2つの箱を一緒の箱にする。箱の番号は前の番号に依存する
        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):#要素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)
while True:
    try:
        listA = list(map(int,input().split()))
        uf.union(listA[0] - 1,listA[1] - 1)
    except:
        break

print(uf.group_count() - 1)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
data = [1 for i in range(m)]
a = []
b = []

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

csr = csr_matrix((data, (a, b)), (n, n))

print(connected_components(csr, return_labels=False) - 1)

Submission status: Accepted

Solution code:
import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n, m = map(int, read().split())
    al = [[] for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        al[a].append(b)
        al[b].append(a)
    cnt = 0
    seen = set()
    for i in range(n):
        if i in seen:
            continue
        todo = [i]
        while todo:
            p = todo.pop()
            if p in seen:
                continue
            seen.add(p)
            todo += al[p]
        cnt += 1
    print(cnt - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy as np
import sys
import math
import collections
par = []
def init(n):
    for i in range(n):
        par.append(i)

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

def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False

def unite(x,y):
    x = root(x)
    y = root(y)
    if x==y:
        return
    par[y] = x
n,m = L()
ab = NL(m)
init(n)
#print(ab)
#print(par)
for a,b in ab:
    unite(a-1,b-1)
    #print(par)

for i in range(len(par)):
    root(i)
#print(par)
count = collections.Counter(par)
print(len(count)-1)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
ad_list = [[] for i in range(n)]
for _ in range(m):
    i, j = map(int, input().split())
    ad_list[i - 1].append(j - 1)
    ad_list[j - 1].append(i - 1)


def bfs(node, ad_list):
    visited = [-1] * node
    queue = deque()
    count = 0
    for i in range(node):
        if visited[i] == 0: continue
        queue.append(i)
        visited[i] = 0
        while queue:
            n = queue.popleft()
            for ad in ad_list[n]:
                if visited[ad] == -1:
                    visited[ad] = 0
                    queue.append(ad)
        count += 1
    return count

ans = bfs(n, ad_list) - 1
print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
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 make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n,m = lr()
uf = UnionFind(n)
for i in range(m):
    a,b = lr()
    a-=1
    b-=1
    uf.union(a,b)
k = len(uf.roots())
print(k-1)

Submission status: Accepted

Solution code:
import collections
import sys


def count_connected_components(max_v, adj_list):
    result = 0
    visited = collections.defaultdict(bool)

    def depth_first_search(start_v):
        visited[start_v] = True
        for v in adj_list[start_v]:
            if not visited[v]:
                depth_first_search(v)
    for u in range(max_v):
        if not visited[u]:
            depth_first_search(u)
            result += 1
    return result


def main():
    sys.setrecursionlimit(50000)
    n, m = map(int, input().split())
    adj_list = collections.defaultdict(set)
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    print(count_connected_components(n, adj_list) - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class union_find():
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[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.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

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1


N,M = map(int,input().split())
g = union_find(N)
group = 0
for i in range(M):
  A,B= map(int,input().split())
  g.unite(A,B)

for j in g.root:
  if j < 0:
    group += 1

print(group - 2)

Submission status: Accepted

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

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 roots(self):
		return [i for i, x in enumerate(self.parents) if x < 0]

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

uf = UnionFind(N)
for _ in range(M):
	a, b = [int(t) - 1 for t in input().split()]
	uf.union(a, b)

ans = uf.group_count() - 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())

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)
print(uf.group_count()-1)

Submission status: Accepted

Solution code:
import types



_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_dsu_code = """
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

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

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        if self.parent_or_size[a] < 0:
            return a

        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))
"""

atcoder.dsu = types.ModuleType('atcoder.dsu')
exec(_atcoder_dsu_code, atcoder.dsu.__dict__)
DSU = atcoder.dsu.DSU

import sys
input = sys.stdin.readline
# from atcoder.dsu import DSU

def main():
    N, M = map(int, sys.stdin.readline().split())
    dsu = DSU(N)
    for _ in range(M):
        A, B = map(int, sys.stdin.readline().split())
        dsu.merge(A-1, B-1)
    print(len(dsu.groups()) - 1)

if __name__ == '__main__':
    main()

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]

  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(len([_ for _ in uf.parent if _ == -1])-1)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
lst = [-1 for i in range(n + 1)]
lst[0] = 0
def find (x):
    if (lst[x] < 0):
        return(x)
    else:
        z = find(lst[x])
        lst[x] = z
        return (z)
def unit(x, y):
    xp = find(x)
    yp = find(y)
    if (xp == yp):
        pass
    else:
        lst[yp] = xp
for i in range(m):
    a, b = map(int,input().split())
    unit(a, b)

ans = -1
for i in range(n + 1):
    if (lst[i] == -1):
        ans = ans + 1

print(ans)

Submission status: Accepted

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

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

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


N, M = map(int, input().split())
par = [-1 for i in range(N)]

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

cnt = -1
num = {0}

for i in par:
  if i <= -1:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
class UnionFind():

    def __init__(self, n):
        # n個の要素
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        要素xのrootを見つける
        """
        if self.parents[x] < 0:
            return x
        else:
            # 再帰的にrootを求める
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        """
        要素x,要素yについて
        rootが同じ場合そのまま
        異なる場合は要素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):
        """
        要素xの集合の大きさを返す
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        要素xと要素yのrootが同じか返す
        """
        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 __str__(self):
        return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))


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

A_B = [list(map(int,input().split())) for _ in range(M)]

union = UnionFind(N)

cnt_town = [False] * M

for a,b in A_B:
  union.unite(a-1,b-1)
print(len(union.roots())-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())
union = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    union.union(A-1,B-1)
print(union.group_count()-1)

Submission status: Accepted

Solution code:
import sys
try:sys.stdin,sys.stdout=open('in.txt','r'),open('out.txt','w')
except:pass
ii1=lambda:int(sys.stdin.readline().strip()) # for interger
is1=lambda:sys.stdin.readline().strip() # for str
iia=lambda:list(map(int,sys.stdin.readline().strip().split())) # for List[int]
isa=lambda:sys.stdin.readline().strip().split() # for List[str]
mod=int(1e9 + 7);from collections import *;from math import *

###################### Start Here ######################

def fun(graph,root):
    visited[root]=True
    queue = deque()
    queue.append(root)
    while len(queue)>0:
        temp = queue[0]
        queue.popleft()
        # print(temp,end=' ')
        for i in range(0,len(graph[temp])):
            if  visited[graph[temp][i]]== False:
                visited[graph[temp][i]] = True
                queue.append(graph[temp][i])
n,m = iia()
graph = [[] for ii in range(n)]
# print(graph)
visited = [False]*(n)
for i in range(m):
    a,b = iia()
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
ans=0
# print(graph)
for i in range(n):
    if visited[i]==False:
        fun(graph,i)
        ans+=1
        # print(ans)
# print(ans)
if ans==1:
    print(0)
else:
    print(ans-1)
# print(visited)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for i in range(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:
            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]

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

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

    @property
    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)

INF = inf
MOD = 1000000007

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()]for j in range(m)]    # nは行数

tmp = 0
res = 0

uf = UnionFind(n)
for i in range(m):
    a = A[i][0] - 1
    b = A[i][1] - 1
    uf.union(a, b)
res = uf.group_count - 1

print(res)

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(10**6)
def dfs(visited,v,adj):
    visited[v]=True 
    for i in adj[v]:
        if not visited[i]:
            dfs(visited,i,adj)  
adj=collections.defaultdict(list)
n,m=map(int,input().split()) 
visited=[False]*n  
for i in range(m):
    u,v=map(int,input().split()) 
    adj[u-1].append(v-1)  
    adj[v-1].append(u-1) 
c=0 
for i in range(n):
    if not visited[i]:
        dfs(visited,i,adj) 
        c+=1 
print(c-1)

Submission status: Accepted

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

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

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

        if x == y:
            return False
        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.root(x)]

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

    def group_count(self):
        return len(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.unite(a, b)


print(uf.group_count() - 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())
AB= [list(map(int,input().split())) for _ in range(M)]

uf = UnionFind(N)
for ab in AB:
    uf.union(ab[0]-1,ab[1]-1)
print(uf.group_count()-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 _ in range(M):
  a,b = map(int,input().split())
  uf.union(a-1,b-1)
  
print(uf.group_count() - 1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    #Union Find

    #xの根を求める
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    #xとyの属する集合の併合
    def unite(x,y):
        x = find(x)
        y = find(y)
        
        if x == y:
            return False
        else:
            #sizeの大きいほうがx
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True

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

    #xが属する集合の個数
    def size(x):
        return -par[find(x)]

    n,m = map(int,input().split())
    #初期化
    #根なら-size,子なら親の頂点
    par = [-1]*n

    for i in range(m):
        X,Y = map(int,input().split())
        unite(X-1,Y-1)
    
    tank = set([])
    for i in range(n):
        tank.add(find(i))
    print(len(tank)-1)

if __name__ == '__main__':
    main()