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 = int(input())
#a, b = map(int,input().split())
#l = list(map(int,input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
from collections import deque
# n = int(input())# ノードの数
n, m = map(int, input().split())

# 隣接リストで格納する
adjl = [[] for _ in range(n+1)]
for i in range(m):  # 隣接関係を受け取る
    a, b = map(int, input().split())
    adjl[a].append(b)
    adjl[b].append(a)

NIL = -1  # 未発見を示す値
d = [-1 for i in range(n+1)]  # 頂点1からの距離を格納するリスト
color = [NIL for i in range(n+1)]  # 未到達かを示すリスト


def bfs(start_node, color_id):  # start_nodeは探索の開始点
    global color, d
    q = deque([start_node])
    d[start_node] = 0
    color[start_node] = color_id
    while len(q) != 0:
        u = q.popleft()
        for v in adjl[u]:
            if color[v] == NIL:
                d[v] = d[u]+1
                color[v] = color_id
                q.append(v)


color_id = 0
for u in range(1, n+1):  # node全てからスタートする
    if color[u] == NIL:
        color_id += 1
        bfs(u, color_id)

colordic = {}
for u in range(1, n+1):
    colordic[color[u]] = True

print(len(colordic)-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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 = [int(x) for x in input().split()]
    AB = [[int(x) for x in input().split()] for _ in range(M)]

    uf = UnionFind(N)

    for a, b in AB:
        uf.union(a - 1, b - 1)

    print(uf.group_count() - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())
class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * (n + 1)
        self.rank = [0] * (n + 1)

    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) -> bool:
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] > self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
        return True

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

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

    def is_same(self, x, y) -> bool:
        return self.root(x) == self.root(y)

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def main():
    N, M = i_map()
    u = UnionFind(N)
    for _ in range(M):
        A, B = i_map()
        u.unite(A, B)
    ans = len(u.roots()) - 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e9))

class uft:
  def __init__(self, N):
    self.__N = N
    self.__arr = [-1] * (N + 1)
  def fp(self, x):
    if self.__arr[x] < 0:
      return x
    else:
      self.__arr[x] = self.fp(self.__arr[x])
      return self.__arr[x]
  def add(self, x, y):
    px = self.fp(x)
    py = self.fp(y)
    if px > py:
      px, py = py, px
    if px == py:
      return 1
    self.__arr[px] += self.__arr[py]
    self.__arr[py] = px
  def groups(self):
    ret = -1
    for i in self.__arr:
      if i < 0:
        ret += 1
    return ret
  def show_arr(self):
    print(self.__arr)
  
N, M = map(int, input().split()) 
UFT = uft(N)

for i in range(M):
  A, B = map(int, input().split())
  UFT.add(A,B)
print(UFT.groups() -1)

Submission status: Accepted

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

arr=[[] for i in range(n+1)]

gro=[0]*(n+1)

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

from collections import deque
deque=deque()

gro_no=0

for i in range(1,n+1):
    if gro[i]==0:
        gro_no+=1
        gro[i]=gro_no
        deque.append(i)

    while deque:
        j=deque.popleft()
        for k in arr[j]:
            if gro[k]==0:
                gro[k]=gro_no
                deque.append(k)

print(gro_no-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 solve():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for i in range(M):
        a,b = map(lambda x: int(x)-1, input().split())
        uf.union(a,b)
    print(uf.group_count() - 1)

if __name__ == '__main__':
    solve()

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)
cnt = 0
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)
for i in uf.parents:
    if i < 0:
        cnt += 1
    
print(cnt - 1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/atc001/tasks/unionfind_a
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 groups(self):
        groups = dict()
        for i in range(self.n):
            p = self.find(i)
            if not groups.get(p):
                groups[p] = set()
            groups[p].add(i)
        return list(groups.values())

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
(N,M),*AB=[list(map(int, x.split())) for x in open(0).readlines() if len(x)>1]

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

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


d=UnionFind(N)
for a,b in AB:
    d.union(a-1,b-1)
print(d.group_count() - 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


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


def main():
    N, M = MI()

    routes = []

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

    for i in range(M):
        a, b = MI()
        cities[a-1].append(b-1)
        cities[b-1].append(a-1)

    groups = [-1] * N

    group = 0

    for i in range(N):
        if groups[i] != -1:
            continue
        deque = cl.deque([i])
        groups[i] = group
        while len(deque) > 0:
            city = deque.popleft()
            next_cities = cities[city]
            for next_city in next_cities:
                if groups[next_city] != -1:
                    continue
                groups[next_city] = group
                deque.append(next_city)

        group += 1

    print(group - 1)


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)

class UnionFind:
    """素集合を木構造として管理する。"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.n = n
        self.cnt = n
 
    def root(self, x):
        """要素xの代表元を求める。O(α(N))"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
 
    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を併合する。O(α(N))"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1
        return True
 
    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める。O(α(N))"""
        return self.root(x) == self.root(y)
 
    def size(self, x):
        """要素xを含む集合の要素数を求める。O(α(N))"""
        return -self.parent[self.root(x)]
 
    def count(self):
        """集合の個数を求める。O(1)"""
        return self.cnt
 
    def groups(self):
        """集合を列挙する。list[list[int]]で返す。O(N)"""
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            res[self.root(i)].append(i)
        return [group for group in res if group]

N,Q = map(int,readline().split())
uf = UnionFind(N)

for _ in range(Q):
    x,y = map(int,readline().split())
    x-=1; y-=1
    uf.merge(x,y)

print(uf.count()-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y] #xにyの個数くっつける 
        par[y] = x #yをxにくっつける
        return 

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

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

N,Q = map(int,readline().split())
#0-index
par = [-1]*N
for _ in range(Q):
    x,y = map(int,readline().split())
    x-=1; y-=1
    union(x,y)

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

Submission status: Accepted

Solution code:
def dfs(node):
  visited[node]=True
  stack=[node]
  while stack:
    node=stack.pop()
    for child in g[node]:
      if visited[child]==False:
        visited[child]=True
        stack.append(child)
n,m=map(int,input().split())
g={i:[] for i in range(1,n+1)}
for i in range(m):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
visited=[False for i in range(n+1)]
c=0
for i in range(1,n+1):
  if visited[i]==False:
    c=c+1
    dfs(i)
print(c-1)

Submission status: Accepted

Solution code:
from sys  import stdin,stdout

from collections import Counter

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

from bisect import bisect_left,bisect_right

mod=1000000007
INF=float('inf')
def DFS(n,d,v):
    v[n]=False
    stack=[n]
    while stack:
        a=stack.pop()
        for i in d[a]:
            if not v[i]:
                stack.append(i)
                v[i]=True
                
def solve():
    n,m=mp()
    d={i:[] for i in range(n+1)}
    for i in range(m):
        a,b=mp()
        d[a].append(b)
        d[b].append(a)
    ans=0
    v=[False for  i in range(n+1)]
    for i in range(1,n+1):
        if not v[i]:
            ans+=1
            DFS(i,d,v)
    pr(ans-1)
    
    
for _ in range(1):

    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a == b:
        pass
    elif Data[a] < Data[b]:
        Data[a] = Data[a] + Data[b]
        Data[b] = a
    else:
        Data[b] = Data[b] + Data[a]
        Data[a] = b 

n, m = map(int, input().split())
UF = [-1 for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    unite(UF, ai, bi)

ans = 0
for i in range(n):
    if UF[i] < 0: ans += 1 
print(ans - 1)

Submission status: Accepted

Solution code:
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

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)

cnt = 0
for item in uf.parents:
    if item < 0:
        cnt += 1

print(cnt-1)

Submission status: Accepted

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

roads=[]

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

group2=[]

while group2!=group:
  group2=list(group)
  for road in roads:
    if group[road[1]-1]>group[road[0]-1]:
      group[road[1]-1]=group[road[0]-1]
    else:
      group[road[0]-1]=group[road[1]-1]
  
counter=1
group.sort()

for i in range(n-1):
  if group[i]!=group[i+1]:
    counter+=1

print(counter-1)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
#import io,os; input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline #for pypy
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

class DisjSet: 
    def __init__(self,n): 
        self.rank = [1]*n 
        self.parent = [i for i in range(n)] 

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

    def Union(self,x,y):
        xset = self.find(x) 
        yset = self.find(y)
        if xset == yset: return

        if self.rank[xset] < self.rank[yset]: 
            self.parent[xset] = yset 
        elif self.rank[xset] > self.rank[yset]: 
            self.parent[yset] = xset 
        else: 
            self.parent[yset] = xset 
            self.rank[xset] += 1

n,m = ip()
obj = DisjSet(n)
for i in range(m):
    a,b = ip()
    obj.Union(a-1,b-1)
dt = {}
for i in range(n):
    p = obj.find(i)
    dt[p] = dt.get(p,0)+1
print(len(dt.keys())-1)

Submission status: Accepted

Solution code:
class UnionFind:
    from typing import List, Set

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n

    def merge(self, x, y) -> int:
        x = self.leader(x)
        y = self.leader(y)

        if x == y:
            return 0

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

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

        return self.parent[x]

    def same(self, x, y) -> bool:
        return self.leader(x) == self.leader(y)

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

    def size(self, x) -> int:
        return -self.parent[self.leader(x)]

    def groups(self) -> List[Set[int]]:
        groups = dict()

        for i in range(self.n):
            p = self.leader(i)
            if not groups.get(p):
                groups[p] = set()
            groups[p].add(i)

        return list(groups.values())


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

    uf = UnionFind(N)

    for _ in range(M):
        # UnionFindを0スタートで実装しているので、入力から1引きます
        A, B = map(lambda x: int(x) - 1, input().split())  
        uf.merge(A, B)  # AとBをmergeします。union, uniteとも呼ばれます。

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'




def solve():
    n, m = map(int, input().split())

    adj_list = {x: [] for x in range(1, n + 1)}

    uf = [x for x in range(n + 1)]
    sz = [1]  * (n + 1)

    def find(i):
        while uf[i] != i:
            uf[i] = uf[uf[i]]
            i = uf[i]
        return i

    def check(i, j):
        return find(i) == find(j)

    def union(i, j):
        a = find(i)
        b = find(j)
        if sz[a] < sz[b]:
            uf[a] = uf[b]
            sz[b] += sz[a]
        else:
            uf[b] = uf[a]
            sz[a] += sz[b]

    for _ in range(m):
        a, b = map(int, input().split())
        if not check(a, b):
            union(a, b)

    sets = 0

    for i in range(1, n + 1):
        if uf[i] == i:
            sets += 1

    cout<<sets - 1<<endl




def main():
    solve()


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())
        
# uf = UnionFind(6)
# print(uf.parents)
# # [-1, -1, -1, -1, -1, -1]

# print(uf)

# print(uf.group_count())

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

uf = UnionFind(n)

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

Submission status: Accepted

Solution code:
from collections import Counter
N, M = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]

    def unite(self, x, y):
        if not self.same(x, y):
            self.root[self.find(y)] = self.find(x)

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
UF = UnionFind(N)
ans = N-1
for _ in range(M):
  x, y = map(int, input().split())
  if not UF.same(x-1, y-1):
    UF.unite(x-1, y-1)
    ans -= 1
print(ans)

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

# from atcoder.dsu import DSU
def solve():
    N,M = map(int,input().split())
    uf = DSU(N)

    for _ in range(M):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        uf.merge(a,b)
    
    print(len(uf.groups())-1)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
f = lambda x: x if p[x]<0 else f(p[x])
N,M = map(int,input().split())
p = [-1]*N
for _ in range(M):
  A,B = map(lambda x:f(int(x)-1),input().split())
  if A==B: continue
  elif A<B: A,B=B,A
  p[A] += p[B]
  p[B] = A
print(sum(i<0 for i in p)-1)

Submission status: Accepted

Solution code:
def f(x):
  while p[x]>0: x = p[x]
  return x
N,M = map(int,input().split())
p = [-1]*N
for _ in range(M):
  A,B = map(lambda x:f(int(x)-1),input().split())
  if A==B: continue
  elif A<B: A,B=B,A
  p[A] += p[B]
  p[B] = A
print(sum(i<0 for i in p)-1)