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:
#!/usr/bin/env python3
class UnionFind:
    """Union-Find(素集合データ構造)"""
    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node
        
        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int):
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
    
    def unite(self, x: int, y: int):
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def same(self, x: int, y: int):
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)
    
    def size(self, x: int) -> bool:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1


def main():
    N, M = map(int, input().split())

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

    ans = -1
    for i in lst.root:
        if i < 0:
            ans += 1
    print(ans)
    # print(lst.root)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = list(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.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 a,b in ab:
    uf.union(a-1,b-1)

print( uf.group_count() - 1 )

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
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:
# 再帰呼び出しのとき付ける
import sys
sys.setrecursionlimit(10**9)

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

n, m = readInt()

root = [-1] * n

def r(x):
    # print("root[x]=",root[x])
    if root[x] < 0:
        # print("r(x)=",x)
        return x
    else:
        root[x] = r(root[x])
        # print(root[x])
        return root[x]

def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x
    # print(root)

def size(x):
    x = r(x)
    # print(x, root[x])
    return -root[x]

for i in range(m):
    x, y = readInt()
    x -= 1
    y -= 1
    unite(x, y)
    # print('size={}'.format(size(i)))

# max_size = 0

# for i in range(n):
#     max_size = max(max_size, size(i))

# print(max_size)

# print(root)
ans = -1
for i in root:
    if i < 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

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

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

	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
		return

n, m = map(int, input().split())
uf = UnionFind(n)
ans = n-1
for _ in range(m):
	a, b = map(int, input().split())
	if uf.find(a-1) != uf.find(b-1):
		ans -= 1
		uf.unite(a-1, b-1)

print(ans)

Submission status: Accepted

Solution code:
import sys

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())
if __name__ == '__main__':
    input = sys.stdin.readline
    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)

    print(uf.group_count()-1)

Submission status: Accepted

Solution code:
class UnionFind:
  par = None
  
  def __init__(self, n):
    self.par = [0] * n
    
  def root(self, x):
    if(self.par[x] == 0):
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.root(self.par[x])
  
  def unite(self, x, y):
    if(self.root(x) != self.root(y)):
      self.par[self.root(x)] = self.root(y)
      
  def same(self, x, y):
    return self.root(x) == self.root(y)
  
N, M = list(map(int, input().split()))
UF = UnionFind(N)
for i in range(M):
  A, B = list(map(int, input().split()))
  UF.unite(A - 1, B - 1) 
ans = 0
for i in range(N):
  if(UF.par[i] == 0):
    ans += 1
print(ans - 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
# from atcoder.dsu import DSU

sys.setrecursionlimit(10**9)

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

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

print(len(d.groups()) - 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m = list(map(int,input().split()))

d = {}
for i in range(m):
    fr, to = list(map(int,input().split()))
    d[fr] = d.get(fr, []) + [to]
    d[to] = d.get(to, []) + [fr]
    
visited = [0 for i in range(n+1)]

def connect(node, i):
    visited[node] = i
    
    if node in d:
        for neig in d[node]:
            if visited[neig] == 0:
                connect(neig, i)
ans = 1
for key in range(1,n+1):
    if visited[key] == 0:
        connect(key, ans)
        ans += 1

print(max(visited)-1)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]
"""
n,k = ip()
x = [inp() for i in range(n)]
"""
import sys
sys.setrecursionlimit(10**6)
def dfs(u):
    global vis,graph
    vis.add(u)
    for i in graph[u]:
        if i not in vis:
            dfs(i)


n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
    graph[b].append(a)
vis = set()
ct = 0
for i in range(1,n+1):
    if i not in vis:
        dfs(i)
        ct += 1
print(ct-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(100001)]
    sys.setrecursionlimit(100001)
    mark=[0]*N
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A-1].append(B-1)
        dic[B-1].append(A-1)


    i=0
    count=0
    while True:
        if not mark[i]:
            count+=1
            d=deque()
            d.appendleft(i)
            while d:
                a=d.popleft()
                mark[a]=1
                for j in dic[a]:
                    if mark[j]:
                        continue
                    
                    d.appendleft(j)
        i+=1
        if i==N:
            break
    
    print(count-1)
main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
#brr=[list(map(int,input().split())) for i in range(M)]
arr=[[] for i in range(N)]

check=[0]*N
ans=[]

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

q=[]
cnt=0
for i in range(N):
    if check[i]==0:
        cnt+=1
    q.append(i)
    #print(cnt,q)
    while q:
        x=q.pop()
        if check[x]==0:
            check[x]=1
            for j in arr[x]:
                q.append(j)
        
print(cnt-1)

Submission status: Accepted

Solution code:
N,M=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+1)
  
for i in range(M):
  a,b=map(int, input().split())
  uf.union(a,b)

print(uf.group_count()-2)

Submission status: Accepted

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

A = [-1 for _ in range(N + 1)]

def search(ls, n):
  while ls[n] > 0:
    n = ls[n]
  return n

for i in range(M):
  a, b = map(int, input().split())
  aa = search(A, a)
  bb = search(A, b)
  if aa != bb:
    A[b] = aa
    A[bb] = aa
    
group = -1
for i in range(1, N + 1):
  if A[i] == -1:
    group += 1
    
print(group)

Submission status: Accepted

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

par = [i for i in range(N)]

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

for a, b in ABs:
    unite(a-1, b-1)

for x in range(N):
    find(x)

print(len(set(par))-1)

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]
route = {int(x): [] for x in range(N)}

for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    route[a].append(b)
    route[b].append(a)

queue = deque()
queue.append(0)

all_town = set([int(x) for x in range(N)])

result = 0
while queue:
    pos = queue.popleft()
    all_town.discard(pos)

    for next_pos in route[pos]:
        if next_pos in all_town:
            queue.append(next_pos)

    if not queue:
        if all_town:
            queue.append(all_town.pop())
            result += 1

print(result)

Submission status: Accepted

Solution code:
def main():


    #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):
        a,b = map(int,input().split())
        unite(a-1,b-1)
    
    tank = set([])
    for i in range(n):
        tank.add(find(i))
    #print(tank)
    print(len(tank)-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#0926
class UnionFind(): # 0インデックス
    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 test(self):
        return self.parents
    def test2(self):
        return sum(z <0 for z in self.parents)
    
N, M = map(int, input().split()) # N人、M個の関係
uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.union(A, B)
    
print(uf.test2()-1)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
    def find(self, x):
        if self.parents[x] == x:
            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
        self.parents[y] = 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)
print(len(set([uf.find(i)for i in range(N)]))-1)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
def r(x):
  while p[x]>=0: x=p[x]
  return x
def u(x,y):
  x,y=r(x),r(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
n,m=f()
p=[-1]*n
for _ in range(m):
  a,b=f()
  u(a-1,b-1)
print(sum(i<0 for i in p)-1)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

n, m = map(int, input().split())
g = defaultdict(list)
s = set(list(range(1, n+1)))
ans = 0

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

while s:
    root = s.pop()
    q = deque()
    q.append(root)
    done = set()
    done.add(root)

    while q:
        node = q.popleft()

        for adj in g[node]:
            if adj not in done:
                done.add(adj)
                q.append(adj)
                s.remove(adj)
    ans += 1

print(ans - 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.rnk = [0]*(n+1)
    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(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.Unite(a,b)
s = set()
for i in range(n):
  s.add(uf.Find_Root(i))
print(len(s)-1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
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()}

uf = UnionFind(N)
for _ in range(M):
    a, b = mapint()
    uf.union(a-1, b-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())
ABs = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

uf = UnionFind(N)

for AB in ABs:
    uf.union(AB[0], AB[1])

print(uf.group_count()-1)

Submission status: Accepted

Solution code:
from collections import deque

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

adjacency_list = [[] for i in range(N)]
for i in range(M):
    tmp = list(map(int, input().split()))
    adjacency_list[tmp[0] - 1].append(tmp[1] - 1)
    adjacency_list[tmp[1] - 1].append(tmp[0] - 1)
con_component = 0
# 接続確認
# print(adjacency_list)
visited_set = set(range(N))
queue = deque()
while visited_set:
    con_component += 1
    queue.append(visited_set.pop())
    while len(queue) != 0:
        ind = queue.popleft()
        # print("start queue", ind)
        for adjacency in adjacency_list[ind]:
            # print("aa",adjacency)
            if adjacency in visited_set:
                visited_set.remove(adjacency)
                queue.append(adjacency)
print(con_component - 1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(idx):
    for x in arr[idx]:
        if not vis[x]:
            vis[x] = True
            dfs(x)


n, m = map(int, input().split())

arr = [[] * (n + 1) for _ in range(n + 1)]
vis = [False] * (n + 1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)

ans = 0

if m == 0:
    print(n-1)
    sys.exit()

dfs(1)
for i in range(2, n + 1):
    if not vis[i]:
        vis[i] = True
        dfs(i)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
visited=[0]*n
def bfs(s):
    q=deque([s])
    visited[s]=1
    while q:
        x=q.popleft()
        for nx in edge[x]:
            if visited[nx]==0:
                visited[nx]=1
                q.append(nx)
    return
ans=0
for s in range(n):
    if visited[s]==0:
        bfs(s)
        ans+=1
print(ans-1)

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]
 
    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size
 
    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x
 
    def is_connected(self, x: int, y: int) -> bool:
        return self[x] == self[y]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x
 
 
import sys
 
readline = sys.stdin.readline
 
N, Q = map(int, readline().split())
tree = UnionFind(N)
res = []
ans=0
for _ in range(Q):
  u, v = map(int, readline().split())
  tree.unite(u-1, v-1)
for u in range(1,N):
  if not tree.is_connected(u, 0):
      ans+=1
      tree.unite(u, 0)
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 same(self, x, y):
        return self.find(x) == self.find(y)
N,M = map(int,input().split())
q = UnionFind(N)

for _ in range(M):
    x,y = map(int,input().split())
    q.union(x-1,y-1)
set_ = set()
cnt = 0
for i in range(N):
    if q.find(i)<0:
        cnt += 1
    else:
        set_.add(q.find(i))
print(cnt + len(set_)-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
F = [[] for _ in range(N)]
P = [0] * N
for i in range(M):
    A, B = map(int, input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
c=0
l = []
for i in range(N):
    if P[i] == 0:
        c+=1
        l.append(i)
        while len(l)>0:
            p=l.pop()
            P[p] = c
            for j in F[p]:
                if P[j] == 0:
                    l.append(j)
print(c-1)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            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

        self.parents[y] = x
        
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)

size = 0
for i in range(n):
    if uf.parents[i] == i:
        size += 1
print(size-1)