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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
parents = [i for i in range(N+1)]

def find(x):
    if x == parents[x]:
        return x
    else:
        x = find(parents[x])
        return x
    
def same(x, y):
    if x==y:
        pass
    else:
        parents[x] = y

for _ in range(M):
    A, B = map(int, input().split())
    x, y = find(A), find(B)
    same(x, y)

print(len(set(parents)) - 2)

Submission status: Runtime Error

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

def find(x):
    if x == parents[x]:
        return x
    else:
        x = find(parents[x])
        return x
    
def same(x, y):
    if x==y:
        pass
    else:
        parents[x] = y

for _ in range(M):
    A, B = map(int, input().split())
    x, y = find(A), find(B)
    same(x, y)

print(len(set(uni.parents)) - 2)

Submission status: Runtime Error

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):
    if x == y:
      return 1
    px = self.fp(x)
    py = self.fp(y)
    if px > py:
      px, py = py, px
    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
  
N, M = map(int, input().split()) 
UFT = uft(N)

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

Submission status: Runtime Error

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):
    if x == y:
      return 1
    px = self.fp(x)
    py = self.fp(y)
    if px > py:
      px, py = py, px
    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
  
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: Runtime Error

Solution code:
import collections
n,m = map(int,input().split())
ans = [0]*n
ans[0]=1
for _ in range(m):
    a,b = map(int,input().split())
    if ans[a]==0 and ans[b]==0:
        if a<b:
            ans[a]=a
            ans[b]=a
        else:
            ans[a]=b
            ans[b]=b
    elif ans[a]!=0 and ans[b]!=0:
        if ans[a]<=ans[b]:
            ans[b]=ans[a]
        elif ans[b]<=ans[a]:
            ans[a]=ans[b]
a=collections.Counter(ans).most_common()
if a[0][0]!=0:
    re= n-a[0][1]
else:
    re=n-a[1][1]
print(re)

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


def solve():
    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)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

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.par=[i for i in range(n)]

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

    def union(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        self.par[rx] = ry

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def count(self):
        return len([0 for i, x in enumerate(self.par) if x == i])

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(int(1e9))
N, M = map(int, input().split())
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):
    if x > y:
      x, y = y, x
    if x == y:
      return 1
    px = self.fp(x)
    py = self.fp(y)
    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
UFT = uft(N)

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
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):
    if x > y:
      x, y = y, x
    if x == y:
      return 1
    px = self.fp(x)
    py = self.fp(y)
    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
UFT = uft(N)

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
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):
    if x > y:
      x, y = y, x
    px = self.fp(x)
    py = self.fp(y)
    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
UFT = uft(N)

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

Submission status: Runtime Error

Solution code:
(N,M),*AB=[list(map(int, x.split())) for x in open(0).readlines() if len(x)>1]
d={}
g=0
for a,b in AB:
    if a in d:
        d[b] = d[a]
    elif b in d:
        b[a] = d[b]
    else:
        g += 1
        d[a] = d[b] = g
for i in range(1,N+1):
    if not i in d:
        g += 1
print(g - 1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
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):
    if x > y:
      x, y = y, x
    px = self.fp(x)
    py = self.fp(y)
    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
UFT = uft(N)

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
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):
    if x > y:
      x, y = y, x
    px = self.fp(x)
    py = self.fp(y)
    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
UFT = uft(N)
for i in range(M):
  A, B = map(int, input().split())
  UFT.add(A,B)
print(UFT.groups() -1)

Submission status: Runtime Error

Solution code:
# -*- coding: Shift-JIS -*-
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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a != b:
        if 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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a != b:
        if 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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a != b:
        if 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())
    unite(UF, ai, bi)

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

Submission status: Runtime Error

Solution code:
class DFS:
    def __init__(self, n, cons):
        nodes = [DFSNode(i) for i in range(n)]
        for i, j in cons:
            nodes[i].addAdjacent(nodes[j])

        self.nodes = nodes

    def clearVisited(self):
        for node in self.nodes:
            node.visited = False

    def execute(self, rootId):
        node = self.nodes[rootId]
        if node.visited:
            return []

        node.visit()
        allNodesId = [node.getId()]
        for adjNode in node.adjacents:
            if not adjNode.visited:
                allNodesId += self.execute(adjNode.id)

        return allNodesId

class DFSNode:
  
    def __init__(self, id):
        self.id = id
        self.visited = False
        self.adjacents = []

    def addAdjacent(self, i):
        self.adjacents.append(i)

    def visit(self):
        self.visited = True

    def getId(self):
        return self.id

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

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

dfs = DFS(n, cons)

nGroup = 0
visitedIds = set()
for i in range(n):
    if i not in visitedIds:
        newVisitedIds = dfs.execute(i)
        visitedIds |= set(newVisitedIds)
        nGroup += 1

print(nGroup - 1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

def unite(Tree, a, b):
    a, b = find(Tree, a), find(Tree, b)
    if a != b:
        if Tree[a] > Tree[b]:
            Tree[a] = Tree[a] + Tree[b]
            Tree[b] = a
        else:
            Tree[b] = Tree[b] + Tree[a]
            Tree[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())
    unite(UF, ai, bi)

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

Submission status: Runtime Error

Solution code:
def find(Tree, x):
    if Tree[x] < 0:
        return x
    else:
        Tree[x] = find(Tree, x)
        return Tree[x] 

def unite(Tree, a, b):
    a, b = find(Tree, a), find(Tree, b)
    if a != b:
        if Tree[a] > Tree[b]:
            Tree[a] = Tree[a] + Tree[b]
            Tree[b] = a
        else:
            Tree[b] = Tree[b] + Tree[a]
            Tree[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())
    unite(UF, ai, bi)

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

Submission status: Runtime Error

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

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

    sets = 0
    visited = {}

    def dfs(curr_node):
        nonlocal visited
        
        visited[curr_node] = True
        for i in adj_list[curr_node]:
            if i not in visited:
                dfs(i)
    
    for i in range(1, n + 1):
        if i not in visited:
            sets += 1
            dfs(i)

    cout<<sets - 1<<endl




def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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
  p[A] += p[B]
  p[B] = A
print(sum(i<0 for i in p)-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())
        
# 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())
    # print(a, b)
    uf.union(a, b)
    
# print(uf.group_count())
print(n - uf.group_count())

Submission status: Runtime Error

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

class MakeSet():
    def __init__(self, x):
        self.parent = x
        self.rank   = 0

def Union(x, y, par):
    xRoot = Find(x, par)
    yRoot = Find(y, par)
    if par[xRoot].rank > par[yRoot].rank:
        par[yRoot].parent = xRoot
    elif par[xRoot].rank < par[yRoot].rank:
        par[xRoot].parent = yRoot
    if xRoot != yRoot: # x と y が同じ集合にない場合だけマージする。
        par[yRoot].parent = xRoot
        par[xRoot].rank += + 1

def Find(x, par):
    if par[x].parent == x:
        return x
    else:
        par[x].parent = Find(par[x].parent, par)
        return par[x].parent

par = [MakeSet(i) for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    Union(a-1, b-1, par)

sets = set([Find(i, par) for i in range(len(par))])
ans = len(sets) - 1
print(ans)

Submission status: Runtime Error

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

Solution code:
from collections import deque
N,M = map(int,input().split())
E = {i: [] for i in range(N)}
for m in range(M):
  A,B = map(int,input().split())
  E[A].append(B)
  E[B].append(A)
  
q = deque([0])
checked = [False]*N
ans = 0
while q and not(all(checked)):
  n = q.popleft()
  if checked[n]: continue
  checked[n] = True
  for i in E[n]:
    if not checked[i]: q.append(i)
  if all(checked): break
  elif not q:
    ans += 1
    for i in range(N):
      if not checked[i]:
        q.append(i)
        break
  
print(ans)

Submission status: Runtime Error

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

roads=[]

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

group2=[]

while group2!=group:
  group2=group
  for road in roads:
    group[road[1]-1]=group[road[0]-1]

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

print(counter-1)

Submission status: Runtime Error

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

roads=[]

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

group2=[]

while group2!=group:
  group2=group
  for road in roads:
    group[road[1]-1]=group[road[0]-1]

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

Submission status: Runtime Error

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

roads=[]

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

group2=[]

while group2!=group:
  group2=group
  for road in roads:
    group[road[1]]=group[road[0]]

print(group[-1])

Submission status: Runtime Error

Solution code:
#(N,M),*AB=[list(map(int, x.split())) for x in open(0).readlines()]
N,M=map(int,input().split())
AB=[list(map(int, input().split())) for _ in range(M)]
d={}
g=0
for a,b in AB:
    if a in d:
        d[b] = d[a]
    elif b in d:
        b[a] = d[b]
    else:
        g += 1
        d[a] = d[b] = g
for i in range(1,N+1):
    if not i in d:
        g += 1
print(g - 1)

Submission status: Runtime Error

Solution code:
(N,M),*AB=[list(map(int, x.split())) for x in open(0).readlines()]
d={}
g=0
for a,b in AB:
    if a in d:
        d[b] = d[a]
    elif b in d:
        b[a] = d[b]
    else:
        g += 1
        d[a] = d[b] = g
for i in range(1,N+1):
    if not i in d:
        g += 1
print(g - 1)

Submission status: Runtime Error

Solution code:
N,M=map(int, input().split())
AB=list(map(int, open(0).read().split()))
ss=[set()]
for i in range(0, len(AB), 2):
    a=AB[i]
    b=AB[i+1]
    for s in ss:
        if a in s or b in s:
            s.add(a)
            s.add(b)
            break
    else:
        ss.add(set([a,b]))
print(N - len(ss) - M)

Submission status: Runtime Error

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

L=[0]*N

for i in range(M):
  A,B=map(int,input().split())
  L[A] +=1
  L[B] +=1
  
print(L.count(0))

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 _ in range(m):
    a , b = map(int,input().split())
    uf.union(a , b)
    
print(len(uf.all_group_members())-1)

Submission status: Runtime Error

Solution code:
def find(n):
    if root[n] < 0:
        return n
    else:
        root[n] = find(root[n])
        return root[n]

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

    root[x] += root[y]
    root[y] = x

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

def same(x,y):
    return find(x) == find(y)

def member(x):
    rt = find(x)
    return [i for i in range(n) if find(i) == rt]

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

def member_count(x):
    return len(roots())

def all_group_members():
    return {r: member(r) for r in roots()}

n , m = map(int,input().split())
root = [-1 for i in range(n)]

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

print(len(all_group_members())-1)

Submission status: Runtime Error

Solution code:
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

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

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  
  #print(r)
  #print("city_a", city_a, "city_b", city_b)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    if city_a_par == city_b_par:
      pass
    else:
      r[city_a_par] = city_b
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

Submission status: Runtime Error

Solution code:
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

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

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  
  print(r)
  print("city_a", city_a, "city_b", city_b)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    if city_a_par == city_b_par:
      pass
    else:
      r[city_a_par] = city_b
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
print(r)
print(group_num-1+r.count(-1)-1)