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:
n,m = list(map(int, input().split()))
parent = list(range(n))

def root(x):
    if parent[x] == x: return x
    rt = root(parent[x])
    parent[x] = rt
    return rt

def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y: return
    parent[y] = x

for _ in range(m):
    a,b = list(map(lambda x: int(x)-1, input().split()))
    unite(a,b)

for i in range(n):
    root(i)

cnt = len(set(parent)) - 1
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())

ans = 0

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

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

    def Unite(self,x,y):
        x = self.Root_Find(x)
        y = self.Root_Find(y)
        if x == y:
            return
        self.root[y] = x

tree = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    tree.Unite(a,b)

for i in range(n+1):
    tree.Root_Find(i)

ans = len(list(set(tree.root))) - 2
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    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)

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

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

def main():
    N, M, *AB = map(int, read().split())
    
    uf = UnionFind(N)
    for a, b in zip(*[iter(AB)] * 2):
        a -= 1
        b -= 1
        uf.union(a, b)
        
    print(uf.group_count() - 1)
    
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
Union-Find Tree / Disjoint Set Union (DSU)
"""


def init_unionfind(N):
    global parent, rank, NUM_VERTEX
    NUM_VERTEX = N
    parent = [-1] * N
    rank = [0] * N


def find_root(x):
    p = parent[x]
    if p == -1:
        return x
    p2 = find_root(p)
    parent[x] = p2
    return p2


def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if x == y:
        return  # already united
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def is_connected(x, y):
    return (find_root(x) == find_root(y))


def num_components():
    return len(set(find_root(x) for x in range(NUM_VERTEX)))

# --- end of library ---


def main_yosupo():
    # verified: https://judge.yosupo.jp/problem/unionfind
    N, Q = [int(x) for x in input().split()]
    init_unionfind(N)
    for q in range(Q):
        typ, u, v = [int(x) for x in input().split()]
        if typ == 0:
            unite(u, v)
        else:
            print(1 if is_connected(u, v) else 0)


def main_abl():
    N, M = map(int, input().split())
    init_unionfind(N)
    for _i in range(M):
        a, b = map(int, input().split())
        unite(a - 1, b - 1)

    print(num_components() - 1)


# tests
T1 = """
3 1
1 2
"""
TEST_T1 = """
>>> as_input(T1)
>>> main_abl()
1
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


if __name__ == "__main__":
    # main_yosupo()
    main_abl()
    # _test()

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(len(set([uf.find(node) for node in range(n)])) - 1)

Submission status: Accepted

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

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
                self.size[x] += self.size[y]
                self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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)
Ans = set()
for i in range(N):
    Ans.add(UF.find(i))
print(len(Ans) - 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7


class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * 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:
            if self.size[x] < self.size[y]:
                x, y = y, x
            self.parents[y] = x
            self.size[x] += self.size[y]


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)
    for i in range(N):
        uf.find(i)
    print(len(set(uf.parents))-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        tank = []
        while par[x] >= 0:
            tank.append(x)
            x = par[x]
        for elt in tank:
            par[elt] = x
        return 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

n,m = map(int, input().split())
par = [-1] * n
for i in range(m):
  a,b = map(int,input().split())
  unite(a-1,b-1)

ans = set([])
for i in range(n):
  ans.add(find(i))
print(len(ans)-1)

Submission status: Accepted

Solution code:
class UnionFindTree:
    """Union-Find Tree

    Attributes:
        n (int):    頂点数
        par (list): 要素の格納先
    """
    def __init__(self, n):
        """初期化 O(1)

        Args:
            n (int): 頂点数
        """
        self.par = [-1] * n

    def find(self, x):
        """要素の検索 O(α(N))

        Args:
            x (int): 対象要素

        Returns:
            int: xの根
        """
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]


    def union(self, x, y):
        """要素の併合 O(1)

        Args:
            x (int): 併合対象の集合に属する要素
            y (int): 併合対象の集合に属する要素
        """
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return

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

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

    def same(self, x, y):
        """要素の判定 O(1)

        Args:
            x (int): 判定対象の要素
            y (int): 判定対象の要素

        Returns:
            bool: xとyが同じ集合に属するか否か
        """
        return self.find(x) == self.find(y)
    
    def size(self, x):
        """要素数の計算 O(1)

        Args:
            x (int): 対象要素

        Returns:
            int: xが属する集合の要素数
        """
        return -self.par[self.find(x)]


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

uf = UnionFindTree(n)

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

s = set()
for i in range(n):
    x = uf.find(i)
    if x not in s:
        s.add(x)

print(len(s) - 1)

Submission status: Accepted

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

dist = [-1]*n
que = deque()
cnt = 0

for i in range(n):
    if dist[i]!=-1:
        continue
    dist[i]=0
    que.append(i)
    while len(que):
        v = que.pop()
        s = G[v]
        for j in s:
            if dist[j]!=-1:
                continue
            dist[j]=0
            que.append(j)
    cnt += 1

print(cnt-1)

Submission status: Accepted

Solution code:
from collections import deque
from sys import stdin
input = stdin.readline

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

graph = [[] for _ in range(N)]
seen = [-1] * N

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


def bfs(x):
    q = deque([])

    q.append(x)
    seen[x] = 1

    while q:
        x = q.popleft()

        for y in graph[x]:
            if seen[y] != -1:
                continue

            seen[y] = 1
            q.append(y)


ans = 0

for i in range(N):
    if seen[i] != -1:
        continue
    else:
        ans += 1
        bfs(i)

print(ans - 1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
#Union-Find木
#par[i]:iの親　deep[i]:iの深さ　size[i]:iの大きさ
par=[i for i in range(n)]
deep=[1]*n
size=[1]*n

#親を見つける
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])

#二つのグループを統合する
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

#xとyが同じグループに属するかどうか
def same(x,y):
  return find(x)==find(y)

#xが属するグループの要素数を返す
def group_count(x):
  return size[find(x)]

#連結成分の個数を返す
def count():
  check=set()
  for i in range(n):
    parent=find(i)
    if parent not in check:
      check.add(parent)
  return len(check)

for i in range(m):
  a,b=map(int,input().split())
  unite(a-1,b-1)
s=count()
print(s-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(lambda x: int(x) - 1, s.split())
    edge[a].append(b)
    edge[b].append(a)

path = [0] * N
cnt = 0
for i in range(N):
    if path[i] == 0:
        cnt += 1
        q = deque()
        path[i] = 1
        q.append(i)
        while q:
            p = q.popleft()
            for np in edge[p]:
                if path[np] == 0:
                    path[np] = 1
                    q.append(np)

print(cnt - 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 readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
class DSU:
    def __init__(self,n):
        self.par=list(range(n))
        self.sz=[1]*(n)
    def find(self,x):
        if x!=self.par[x]:
            self.par[x]=self.find(self.par[x])
        return self.par[x]
    def union(self,x,y):
        x,y=self.find(x),self.find(y)
        if x!=y:
            if self.sz[y]>self.sz[x]:
                x,y=y,x
            self.par[y]=x
            self.sz[x]+=self.sz[y]
            self.sz[y]=self.sz[x]
            return True
        return False
    def parent(self,x):
        return self.par[x]

def solve(N,A):
    dsu=DSU(N)
    for a,b in A:
        dsu.union(a-1,b-1)
    cnt=0
    for i in range(N):
        if dsu.parent(i)==i:
            cnt+=1
    return cnt-1



N,M=readMap()
A=[]
for _ in range(M):
    a,b=readMap()
    A.append((a,b))
print(solve(N,A))

Submission status: Accepted

Solution code:
code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/ac-library]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp cimport bool
from libc.stdio cimport getchar, printf
from libcpp.string cimport string
from libcpp.vector cimport vector
cdef extern from "<atcoder/dsu>" namespace "atcoder":
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()

cdef class Dsu:
    cdef dsu *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new dsu(n)
    cpdef int merge(self, int a, int b):
        return self._thisptr.merge(a, b)
    cpdef bool same(self, int a, int b):
        return self._thisptr.same(a, b)
    cpdef int leader(self, int a):
        return self._thisptr.leader(a)
    cpdef int size(self, int a):
        return self._thisptr.size(a)
    cpdef vector[vector[int]] groups(self):
        return self._thisptr.groups()

cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import Dsu, ReadInt

def main():
    N,M = ReadInt(2)
    dsu = Dsu(N)
    for i in range(M):
        a,b = ReadInt(2)
        dsu.merge(a-1,b-1)
    print(len(dsu.groups())-1)

if __name__ == "__main__":
    main()