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

Submission status: Accepted

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

    def find(self, node):
        if self.parent[node] < 0:
            return node
        self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, node1, node2):
        node1 = self.find(node1)
        node2 = self.find(node2)
        if node1 == node2:
            return
        if self.parent[node1] > self.parent[node2]:
            node1, node2 = node2, node1
        self.parent[node1] += self.parent[node2]
        self.parent[node2] = node1
        return

    def same(self, node1, node2):
        return self.find(node1) == self.find(node2)

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

    def roots(self):
        return [i for i, x in enumerate(self.parent) 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.union(a, b)

print(uf.group_count() - 1)

Submission status: Accepted

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

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

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

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

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

par = [-1]*n

for a, b in ab:
    unite(a, b)

nset=set()
for i in range(n):
    if not find(i) in nset:
        nset.add(find(i))
else:
    print(len(nset)-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.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())
uni = UnionFind(n)
for i in range(m):
    a, b = ab[i]
    uni.union(a - 1, b - 1)
print(uni.group_count() - 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

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

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

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

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


def main():
    n, m = map(int, input().split())
    UF = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        UF.Unite(a, b)

    print(UF.group_count() - 2)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import Counter

class UnionFind:
    def __init__(self, N):
        self.root = [n for n in range(N)]

    def get_root(self, x):
        if self.root[x] == x:
            return x
        else:
            self.root[x] = self.get_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        if root_x != root_y:
            self.root[root_x] = root_y


    def final(self):
        for i in range(N):
            root_r = self.get_root(self.root[i])
            if root_r != self.root[i]:
                self.root[self.root[i]] = root_r

def main(N, M, AB):
    uf = UnionFind(N)
    {uf.unite(*ab) for ab in AB}
    c = Counter(map(uf.get_root, uf.root))
    print(len(c) - 1)

if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    AB = {tuple(map(lambda x:int(x)-1, input().split())) for m in range(M)}
    main(N, M, AB)

Submission status: Accepted

Solution code:
import queue
n, m = map(int, input().split())
a = [[] for _ in range(n)]
ans = 0
 
for _ in range(m):
    x, y = map(int, input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)
 
route = set()
route.add(0)
q = queue.Queue()
q.put(0)
 
for i in range(n):
    if not i in route:
        route.add(i)
        q.put(i)
        ans += 1
    while not q.empty():
        c = q.get()
        for k in a[c]:
            if not k in route:
                q.put(k)
                route.add(k)
    if len(route) == n:
        print(ans)
        break

Submission status: Accepted

Solution code:
# Union-Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n + 1)]

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return 0
        elif x < y:
            self.parents[y] = x
        else:
            self.parents[x] = y
        return 1

from collections import Counter
n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)
    
roots = []
for num in uf.parents:
    roots.append(uf.find(num))
roots.pop(0)

mn = Counter(roots)
print(len(mn)-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

n,m = map(int, sys.stdin.readline().rstrip("\n").split())
bridges = [[] for _ in range(n)]
done = [False]*n
for _ in range(m):
    a,b = map(int, sys.stdin.readline().rstrip("\n").split())
    bridges[a-1].append(b-1)
    bridges[b-1].append(a-1)
d = deque()
ans = -1
for i in range(n):
    if not done[i]:
        done[i] = True
        d.append(i)
        while d:
            cp = d.pop()
            for np in bridges[cp]:
                if not done[np]:
                    done[np] = True
                    d.append(np)
        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())

n,m=map(int,input().split())
uf=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
ans = 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 _ 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:
import sys
sys.setrecursionlimit(100000)

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

A = []
B = []

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)

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

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

def unite(x, y):
    x = find(x)
    y = find(y)
    root[y] = x

for i in range(M):
    unite(A[i], B[i])

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

roots = set(root)

print(len(roots) - 1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
par=[i for i in range(n+1)]
def find(x):
    if par[x] == x:
        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 0
    par[x] = y
for i in range(m):
    a,b=map(int,input().split())
    unite(a,b)
ans=[find(i) for i in range(1,n+1)]
ans=set(ans)
print(len(ans)-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

def bfs(s):
  q = [s]
  while q != []:
    p = q[0]
    del q[0]
    for node in adj[p]:
      if not visited[node]:
        visited[node] = True
        q.append(node)

n,m = map(int,input().split())
adj = defaultdict(list)
visited = [False]*(n+1)
comp = 0
for _ in range(m):
  a,b = map(int,input().split())
  adj[a].append(b)
  adj[b].append(a)
for i in range(1,n+1):
  if not visited[i]:
    comp+=1
    bfs(i)
print(comp-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 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())
  uf.union(A-1,B-1)

print(uf.group_count()-1)

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-09-26 20:17
# @url:
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
from decimal import *
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
## 注意嵌套括号!!!!!!
## 先有思路,再写代码,别着急!!!
## 先有朴素解法,不要有思维定式,试着换思路解决
def main():
    n,m=map(int,input().split())
    s=set()
    fa=[i for i in range(n+1)]
    child_sum=[1]*(n+1)
    # 并查集常用函数
    def find(x):
        if x!=fa[x]:
            fa[x]=find(fa[x])
        return fa[x]
    def union(x,y):
        x = find(x)
        y = find(y)
        if x == y:  
            return
        fa[x] = y
        # 计算并查集的交集大小
        child_sum[y]+=child_sum[x]
    pairs=[]
    for i in range(m):
        a=list(map(int,input().split()))
        pairs.append((a[0],a[1]))
    # 求并集
    for (i,j) in pairs:
        union(i,j)
    for (i,j) in pairs:
        union(j,i)
    # print (fa)
    for i in range(1,n+1):
        s.add(fa[i])
    print (len(s)-1)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# 幅優先探索（行きがけ）
import collections
import sys
import copy
import re
import math


def I(): return int(sys.stdin.readline().rstrip())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def S(): return sys.stdin.readline().rstrip()


def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N,M = LI()
    loadArray = [LI() for _ in range(M)]

    ans = 0

    class UnionFind():
        #クラスコンストラクタ
        #selfはインスタンス自身
        def __init__(self, n):
            #親ノードを-1に初期化する
            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]

        #xとyの木を併合する
        def union(self, x, y):
            #x,yの根をX,Yとする
            X = self.find(x)
            Y = self.find(y) 

            #根が同じなら結合済み
            if X == Y:
                return
            #ノード数が多い方をXとする
            if self.parents[X] > self.parents[Y]:
                X, Y = Y, X

            #XにYのノード数を足す
            self.parents[X] += self.parents[Y]
            #Yの根を X>0 とする
            self.parents[Y] = X

    uf = UnionFind(N)
    for a, b in loadArray:
        #インデックスを調整し、a,bの木を結合
        a -= 1; b -= 1
        uf.union(a, b)

    for u in uf.parents:
        if u<0:
            ans += 1

    

    print(ans-1)


if __name__ == '__main__':
    main()

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


def solve(N, paths) -> int:
    uf = UnionFind(N)
    for x, y in paths:
        uf.union(x - 1, y - 1)
    return uf.group_count() - 1


if __name__ == '__main__':
    main()

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

#c
# from atcoder import dsu
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ds = dsu.DSU(n)
for i in ab:
    ds.merge(i[0]-1,i[1]-1)
    
s = ds.groups()

print(len(s)-1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
from sys import stdin


def makeConnected(n, connections):
    l = list(zip(*connections))
    d = [1] * len(connections)
    a = csr_matrix((d, (l[0], l[1])), (n, n))
    return connected_components(a, return_labels=0)


def main():
    input = lambda: stdin.readline()[:-1]
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]

    ab = [[a - 1, b - 1] for a, b in AB]
    ans = makeConnected(N, ab) - 1
    print(ans)


main()

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 m in range(M)]
UF = UnionFind(N)

for A,B in AB:
  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())
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:
N, M = map(int, input().split())
Pajew = [i for i in range(N)]
import sys
sys.setrecursionlimit(1000000)

def find(x, Pajew):
    if Pajew[x] == x:
        return x
    else:
        a = find(Pajew[x], Pajew)
        Pajew[x] =a
        return a

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

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

grou = 0
for i in range(N):
    if i == Pajew[i]:
        grou +=1


print(grou-1)

Submission status: Accepted

Solution code:
class disjoint_set:
    def __init__(self,num):

        self.array=[0]+[[i,0] for i in range(1,num+1)]  # our set
    
    def union(self,a,b):
        
        ''' a and b are the vertices that we want to connect them to each other '''
        
        a=self.find(a) # finds the ancestor of a
        b=self.find(b) # finds the ancestor of b
    
        if a==b:
            # if the ancestors of a and b are the same , do nothing
            return False
    

        # connecting two graph components to each other

        if self.array[a][1] > self.array[b][1] :
            self.array[b][0]=a
        
        elif self.array[a][1] < self.array[b][1] :
            self.array[a][0]=b

        else:
            self.array[a][0]=b
            self.array[b][1]+=1
        return True
            
    def find(self,a):
        p=[]
        while self.array[a][0]!=a :
            p.append(a)
            a=self.array[a][0]
        for i in p:
            self.array[i][0]=a
        return a

##############################3
n,m=map(int,input().split())
dset=disjoint_set(n)
for _ in range(m):
    a,b=map(int,input().split())
    dset.union(a,b)

ans=set()
for i in range(1,n+1) :
    ans.add(dset.find(i))

print(len(ans)-1)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
ls = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  ls[A-1].append(B-1)
  ls[B-1].append(A-1)
visited = [False]*N
tmp = 0
counter = 0
isl = 0
while True:
  isl += 1
  found = deque()
  for city in ls[tmp]:
    found.append(city)
  visited[tmp] = True
  while len(found) != 0:
    tmp = found.pop()
    if not visited[tmp]:
      for city_ in ls[tmp]:
        found.append(city_)
      visited[tmp] = True
  while visited[counter]:
    counter += 1
    if counter > N-1:
      break
  tmp = counter
  if tmp > N-1:
    break
print(isl-1)

Submission status: Accepted

Solution code:
import numpy as np
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)