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: Runtime Error

Solution code:
#Code by Sounak, IIESTS
#------------------------------warmup----------------------------

import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading




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")

#-------------------game starts now-----------------------------------------------------
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]
 
    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]
 
    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]
 
    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]
 
 
class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)
 
    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
#-------------------------------------------------------------------------
n,m=map(int,input().split())
visited=[0]*n
d=defaultdict(list)
def dfs(n):
    visited[n]=1
    #print(visited)
    for i in d[n]:
        if visited[i]==0:
            dfs(i)

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

r=-1
for i in range (n):
    if visited[i]==0:
        dfs(i)
        r+=1
print(r)

Submission status: Runtime Error

Solution code:
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
 b,a=sorted(map(r:=lambda x:x*(p[x]<0)or r(p[x]),a),key=p.__getitem__)
 if a-b:p[a]+=p[b];p[b]=a
print(sum(i<0for i in p)-2)

Submission status: Runtime Error

Solution code:
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
 a,b=map(r:=lambda x:x*(p[x]<0)or r(p[x]),a)
 if a-b:p[a]+=p[b];p[b]=a
print(sum(i<0for i in p)-2)

Submission status: Runtime Error

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())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

checked = [False]*n
q = deque([])
cnt = 0

#連結成分のカウント

for i in range(n):
    if checked[i]:
        continue
    checked[i] = True
    q.append(i)
    while q:
        v = q.pop()
        s = g[v]
        for j in s:
            if checked[j]:
                continue
            checked[j] = True
            q.append(j)
    cnt += 1

print(cnt - 1

Submission status: Runtime Error

Solution code:

from collections import defaultdict
visited=set()
def dfs(visited,graph,node):
	if node not in visited:
		visited.add(node)
		for neighbour in graph[node]:
			dfs(visited,graph,neighbour)


n,m=map(int,input().split())
d=defaultdict(list)


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




dfs(visited,d,m)

print(n-len(visited))

Submission status: Runtime Error

Solution code:

from collections import defaultdict
visited=set()
def dfs(visited,graph,node):
	if node not in visited:
		visited.add(node)
		for neighbour in graph[node]:
			dfs(visited,graph,neighbour)


n,m=map(int,input().split())
d=defaultdict(list)


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



dfs(visited,d,1)

print(n-len(visited))

Submission status: Runtime Error

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)

    return num_components() - 1


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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,n):
        self.param  = [-1]*N
        self.tree   = [0]*N
        
    def clustering(self,x,y):
        x ,y =min(x,y), max(x,y)
        #小さいほうが未知
        if self.param[x] == -1:
            #どちらも未知
            if self.param[y] == -1:
                self.param[x] = y
                self.param[y] = y
                self.tree[y] = [x,y]
            #小さいほうだけ未知
            else:
                self.param[y] = self.param[x]
                self.tree[self.param[y]].append(x)
                
        #小さいほうが既知
        else:
            #大きいほうだけ未知
            if self.param[y] == -1:
                self.param[y] = self.param[x]
                self.tree[self.param[x]].append(y)
            #x,yが既知(長いほうを優先して残す)
            else:
                if self.param[x] == self.param[y]:
                    pass
                
                else:
                    if len(self.tree[self.param[x]]) > len(self.tree[self.param[y]]):
                        big   = x
                        small = y
                    else:
                        big   = y
                        small = x

                    self.tree[self.param[big]]  = self.tree[self.param[big]]+self.tree[self.param[small]]
                    small_ = self.param[small]
                    for i in self.tree[self.param[small]]:
                        self.param[i] = self.param[big]

                    self.tree[small_] = 0

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    uf.clustering(A-1,B-1)
    #print(uf.tree)
    #print(uf.param)
    

a = list(set(uf.param))
sum_ = 0
sub = 0
for i in range(len(a)):
    if a[i]==-1:
        pass
    else:
        sub += 1
        sum_ += len(uf.tree[a[i]])

print(N - sum_ + sub - 1)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,n):
        self.param  = [-1]*N
        self.tree   = [0]*N
        
    def clustering(self,x,y):
        x ,y =min(x,y), max(x,y)
        #小さいほうが未知
        if self.param[x] == -1:
            #どちらも未知
            if self.param[y] == -1:
                self.param[x] = y
                self.param[y] = y
                self.tree[y] = [x,y]
            #小さいほうだけ未知
            else:
                self.param[y] = self.param[x]
                self.tree[self.param[y]].append(x)
                
        #小さいほうが既知
        else:
            #大きいほうだけ未知
            if self.param[y] == -1:
                self.param[y] = self.param[x]
                self.tree[self.param[x]].append(y)
            #x,yが既知(長いほうを優先して残す)
            else:
                if len(self.tree[self.param[x]]) >= len(self.tree[self.param[y]]):
                    big   = x
                    small = y
                else:
                    big   = y
                    small = x
                    
                self.tree[self.param[big]]  = self.tree[self.param[big]]+self.tree[self.param[small]]
                small_ = self.param[small]
                for i in self.tree[self.param[small]]:
                    self.param[i] = self.param[big]
                    
                self.tree[small_] = 0

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    uf.clustering(A-1,B-1)
    #print(uf.tree)
    #print(uf.param)
    

a = list(set(uf.param))
sum_ = 0
sub = 0
for i in range(len(a)):
    if a[i]==-1:
        pass
    else:
        sub += 1
        sum_ += len(uf.tree[a[i]])

print(N - sum_ + sub - 1)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
cnt = 0
dl = []
for i in range(m):
  x,y = map(int,input().split())
  if i == 0:
    a.append([])
    a[0].append(x)
    a[0].append(y)
  else:
    f = -1
    for j in range(len(a)):
      if f == -1 and (x in a[j] or y in a[j]):
        a[j].append(x)
        a[j].append(y)
        f = i
      elif f != -1 and len(set(a[f])&a[j])>0:
        a[f] += a[j]
        a[f] = list(set(a[f]))
        di.append(j)
      elif j == len(a)-1:
        a.append([x,y])
    for i in reversed(dl):
      del a[i]
    dl = []
nl = []
for i in range(len(a)):
  nl += a[i]
nl = set(nl)
print(len(a)-1+n-len(nl))

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,n):
        self.param  = [-1]*N
        self.tree   = [0]*N
        
    def clustering(self,x,y):
        x ,y =min(x,y), max(x,y)
        #小さいほうが未知
        if self.param[x] == -1:
            #どちらも未知
            if self.param[y] == -1:
                self.param[x] = y
                self.param[y] = y
                self.tree[y] = [x,y]
            #小さいほうだけ未知
            else:
                self.param[y] = self.param[x]
                self.tree[self.param[y]].append(x)
                
        #大きいほうが未知
        else:
            #大きいほうだけ未知
            if self.param[y] == -1:
                self.param[x] = self.param[y]
                self.tree[self.param[x]].append(y)
            #x,yが既知(長いほうを優先して残す)
            else:
                if len(self.tree[self.param[x]]) >= len(self.tree[self.param[y]]):
                    big   = x
                    small = y
                else:
                    big   = y
                    small = x
                    
                self.tree[self.param[big]]  = self.tree[self.param[big]]+self.tree[self.param[small]]
                small_ = self.param[small]
                for i in self.tree[self.param[small]]:
                    self.param[i] = self.param[big]
                    
                self.tree[small_] = 0

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    uf.clustering(A-1,B-1)
    #print(uf.tree)
    #print(uf.param)
    

a = list(set(uf.param))
sum_ = 0
sub = 0
for i in range(len(a)):
    if a[i]==-1:
        pass
    else:
        sub += 1
        sum_ += len(uf.tree[a[i]])

print(N - sum_ + sub - 1)

Submission status: Runtime Error

Solution code:
#![allow(dead_code,unused_variables)]
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
    }
    let mut uf = Dsu::new(n);
    for i in 0..m{
        input!(a:usize,b:usize);
        uf.merge(a-1,b-1);
    }
    println!("{}",uf.groups().len()-1);
}
//https://github.com/rust-lang-ja/ac-library-rs

pub mod dsu {
    /// Implement (union by size) + (path compression)
    /// Reference:
    /// Zvi Galil and Giuseppe F. Italiano,
    /// Data structures and algorithms for disjoint set union problems
    pub struct Dsu {
        n: usize,
        // root node: -1 * component size
        // otherwise: parent
        parent_or_size: Vec<i32>,
    }

    impl Dsu {
        // 0 <= size <= 10^8 is constrained.
        pub fn new(size: usize) -> Self {
            Self {
                n: size,
                parent_or_size: vec![-1; size],
            }
        }
        pub fn merge(&mut self, a: usize, b: usize) -> usize {
            assert!(a < self.n);
            assert!(b < self.n);
            let (mut x, mut y) = (self.leader(a), self.leader(b));
            if x == y {
                return x;
            }
            if -self.parent_or_size[x] < -self.parent_or_size[y] {
                std::mem::swap(&mut x, &mut y);
            }
            self.parent_or_size[x] += self.parent_or_size[y];
            self.parent_or_size[y] = x as i32;
            x
        }

        pub fn same(&mut self, a: usize, b: usize) -> bool {
            assert!(a < self.n);
            assert!(b < self.n);
            self.leader(a) == self.leader(b)
        }
        pub fn leader(&mut self, a: usize) -> usize {
            assert!(a < self.n);
            if self.parent_or_size[a] < 0 {
                return a;
            }
            self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;
            self.parent_or_size[a] as usize
        }
        pub fn size(&mut self, a: usize) -> usize {
            assert!(a < self.n);
            let x = self.leader(a);
            -self.parent_or_size[x] as usize
        }
        pub fn groups(&mut self) -> Vec<Vec<usize>> {
            let mut leader_buf = vec![0; self.n];
            let mut group_size = vec![0; self.n];
            for i in 0..self.n {
                leader_buf[i] = self.leader(i);
                group_size[leader_buf[i]] += 1;
            }
            let mut result = vec![Vec::new(); self.n];
            for i in 0..self.n {
                result[i].reserve(group_size[i]);
            }
            for i in 0..self.n {
                result[leader_buf[i]].push(i);
            }
            result
                .into_iter()
                .filter(|x| !x.is_empty())
                .collect::<Vec<Vec<usize>>>()
        }
    }

    #[cfg(test)]
    mod tests {
        use super::*;

        #[test]
        fn dsu_works() {
            let mut d = Dsu::new(4);
            d.merge(0, 1);
            assert_eq!(d.same(0, 1), true);
            d.merge(1, 2);
            assert_eq!(d.same(0, 2), true);
            assert_eq!(d.size(0), 3);
            assert_eq!(d.same(0, 3), false);
            assert_eq!(d.groups(), vec![vec![0, 1, 2], vec![3]]);
        }
    }
}
use dsu::*;

Submission status: Runtime Error

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 par:
    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,b)
print(count()-1)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,n):
        self.param  = [-1]*N
        self.tree   = [0]*N
        
    def clustering(self,x,y):
        x ,y =min(x,y), max(x,y)
        #小さいほうが未知
        if self.param[x] == -1:
            #どちらも未知
            if self.param[y] == -1:
                self.param[x] = y
                self.param[y] = y
                self.tree[y] = [x,y]
            #小さいほうだけ未知
            else:
                self.param[x] = self.param[y]
                self.tree[self.param[y]].append(x)
                
        #大きいほうが未知
        else:
            #大きいほうだけ未知
            if self.param[y] == -1:
                self.param[y] = x
                self.tree[self.param[x]].append(y)
            #x,yが既知(長いほうを優先して残す)
            else:
                if len(self.tree[self.param[x]]) >= len(self.tree[self.param[y]]):
                    big   = x
                    small = y
                else:
                    big   = y
                    small = x
                    
                self.tree[self.param[big]]  = self.tree[self.param[big]]+self.tree[self.param[small]]
                small_ = self.param[small]
                for i in self.tree[self.param[small]]:
                    self.param[i] = self.param[big]
                    
                self.tree[small_] = 0

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    uf.clustering(A-1,B-1)
    

a = list(set(uf.param))
sum_ = 0
sub = 0
for i in range(len(a)):
    if a[i]==-1:
        pass
    else:
        sub += 1
        sum_ += len(uf.tree[a[i]])

print(N - sum_ + sub - 1)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,n):
        self.param  = [-1]*N
        self.tree   = [0]*N
        
    def clustering(self,x,y):
        x ,y =min(x,y), max(x,y)
        #小さいほうが未知
        if self.param[x] == -1:
            #どちらも未知
            if self.param[y] == -1:
                self.param[x] = y
                self.param[y] = y
                self.tree[y] = [x,y]
            #小さいほうだけ未知
            else:
                self.param[x] = self.param[y]
                self.tree[self.param[y]].append(x)
                
        #大きいほうが未知
        else:
            #大きいほうだけ未知
            if self.param[y] == -1:
                self.param[y] = x
                self.tree[self.param[x]].append(y)
            #x,yが既知(長いほうを優先して残す)
            else:
                if len(self.tree[self.param[x]]) >= len(self.tree[self.param[y]]):
                    big   = x
                    small = y
                else:
                    big   = y
                    small = x
                    
                self.tree[self.param[big]]  = self.tree[self.param[big]]+self.tree[self.param[small]]
                small_ = self.param[small]
                for i in self.tree[self.param[small]]:
                    self.param[i] = self.param[big]
                    
                self.tree[small_] = 0

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    uf.clustering(A-1,B-1)
    print(uf.tree)
    print(uf.param)
    

a = list(set(uf.param))
sum_ = 0
sub = 0
for i in range(len(a)):
    if a[i]==-1:
        pass
    else:
        sub += 1
        sum_ += len(uf.tree[a[i]])

print(N - sum_ + sub - 1)

Submission status: Runtime Error

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

class UnionFind:
    def __init__(self,n):
        self.param  = [-1]*N
        self.tree   = [0]*N
        
    def unite(self,x,y):
        pass 
    
    #親を探す
    def search(self,x,y):
        pass
    
    def clustering(self,x,y):
        x ,y =min(x,y), max(x,y)
        #小さいほうが未知
        if self.param[x] == -1:
            #どちらも未知
            if self.param[y] == -1:
                self.param[x] = y
                self.param[y] = y
                self.tree[y] = [x,y]
            #小さいほうだけ未知
            else:
                self.param[x] = self.param[y]
                self.tree[self.param[y]].append(x)
                
        #大きいほうが未知
        else:
            #大きいほうだけ未知
            if self.param[y] == -1:
                self.param[y] = x
                self.tree[self.param[x]].append(y)
            #x,yが既知(長いほうを優先して残す)
            else:
                if len(self.tree[self.param[x]]) >= len(self.tree[self.param[y]]):
                    big   = x
                    small = y
                else:
                    big   = y
                    small = x
                    
                self.tree[self.param[big]]  = self.tree[self.param[big]]+self.tree[self.param[small]]
                small_ = self.param[small]
                for i in self.tree[self.param[small]]:
                    self.param[i] = self.param[big]
                    
                self.tree[small_] = 0
                
uf = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    A,B = A-1, B-1
    uf.clustering(A,B)
    #print(uf.tree)
    #print(uf.param)
    
    
a = list(set(uf.param))
sum_ = 0
sub = 0
for i in range(len(a)):
    if a[i]==-1:
        pass
    else:
        sub += 1
        sum_ += len(uf.tree[a[i]])

print(N - sum_ + sub - 1)

Submission status: Runtime Error

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

nodes = [_ for _ in range(n)]
group = [1]*n

def dfs(node, group):
    s = li[node]
    group[node]=0
    for v in s:
        if group[v]!=0:
            dfs(v, group)

cnt = 0       
for i in range(n):
    if group[i]!=0:
        dfs(i,group)
        cnt += 1

print(cnt-1)

Submission status: Runtime Error

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

class UnionFind:
    def __init__(self,n):
        self.param  = [-1]*N
        self.tree   = [0]*N
        
    def unite(self,x,y):
        pass 
    
    #親を探す
    def search(self,x,y):
        pass
    
    def clustering(self,x,y):
        x ,y =min(x,y), max(x,y)
        #小さいほうが未知
        if self.param[x] == -1:
            #どちらも未知
            if self.param[y] == -1:
                self.param[x] = y
                self.param[y] = y
                self.tree[y] = [x,y]
            #小さいほうだけ未知
            else:
                self.param[x] = self.param[y]
                self.tree[self.param[y]].append(x)
                
        #大きいほうが未知
        else:
            #大きいほうだけ未知
            if self.param[y] == -1:
                self.param[y] = x
                self.tree[self.param[x]].append(y)
            #x,yが既知(長いほうを優先して残す)
            else:
                if len(self.tree[self.param[x]]) >= len(self.tree[self.param[y]]):
                    big   = x
                    small = y
                else:
                    big   = y
                    small = x
                    
                self.tree[self.param[big]]  = self.tree[self.param[big]]+self.tree[self.param[small]]
                small_ = self.param[small]
                for i in self.tree[self.param[small]]:
                    self.param[i] = self.param[big]
                    
                self.tree[small_] = 0
                
uf = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    uf.clustering(A,B)
    #print(uf.tree)
    #print(uf.param)
    
    
a = list(set(uf.param))
sum_ = 0
sub = 0
for i in range(len(a)):
    if a[i]==-1:
        pass
    else:
        sub += 1
        sum_ += len(uf.tree[a[i]])

print(N - sum_ + sub - 1)

Submission status: Runtime Error

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

nodes = [i for i in range(n)]
group = [1]*n

def dfs(node, group):
    s = li[node]
    group[node]=0
    for v in s:
        if group[v]!=0:
            dfs(v, group)

cnt = 0       
for i in range(n):
    if group[i]!=0:
        dfs(i,group)
        cnt += 1

print(cnt-1)

Submission status: Runtime Error

Solution code:
def root(x):
  if r[x] < 0:
    return x
  else:
    r[x] = root(r[x])
    return r[x]

from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, x in enumerate(road):
  x1_me = x[0]
  x2_me= x[1]
  x1 = root(x1_me)
  x2 = root(x2_me)
  #print("x1", x1, "x2", x2)
  
  if r[x1] == -1 and r[x2] == -1:
    r[x2] = x1
  elif r[x1] == -1 or r[x2] == -1:
    if r[x1] > r[x2]:
      r[x2] = r[x1]
    else:
      r[x1] = r[x2]
  else:
    if r[x1] > r[x2]:
      r[x1] = r[x2]
    else:
      r[x2] = r[x1]
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)