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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

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

for i in range(M):
  A,B = map(int,input().split())
  uf.union(A,B)

print(uf.group_count()-1)

Submission status: Runtime Error

Solution code:
# Python3 program to print DFS traversal
# from a given given graph
from collections import defaultdict

viz = [0]*100005
# This class represents a directed graph using
# adjacency list representation


class Graph:

    # Constructor
    def __init__(self):

        # default dictionary to store graph
        self.graph = defaultdict(list)

    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)

    # A function used by DFS
    def DFSUtil(self, v, visited):
        global viz
        # Mark the current node as visited
        # and print it
        visited[v] = True
        viz[v]=1
        # print(v, end=' ')

        # Recur for all the vertices
        # adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)

    # The function to do DFS traversal. It uses
    # recursive DFSUtil()
    def DFS(self, v,visited):

        # Mark all the vertices as not visited
        # visited = [False] * (max(self.graph)+1)

        # Call the recursive helper function
        # to print DFS traversal
        self.DFSUtil(v, visited)

        return visited

# Driver code


# Create a graph given
# in the above diagram

    
g = Graph()
n, m = map(int, input().split())
vizi=[False]*(n+1)
for i in range(m):
    a, b = map(int, input().split())
    g.addEdge(a, b)
    g.addEdge(b, a)

cnt = 0
vizi=g.DFS(0,vizi)
for i in range(1,n):
    if vizi[i] == False:
        cnt += 1
        vizi=g.DFS(i,vizi)

print(cnt)

# print("Following is DFS from (starting from vertex 2)")
# g.DFS(2)

# This code is contributed by Neelam Yadav

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict

n, m = map(int, input().split())
g = defaultdict(list)
s = set(list(range(1, n+1)))
ans = 0

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

while s:
    root = s.pop()
    q = deque()
    q.append(root)
    done = set()
    done.add(root)

    while q:
        node = q.popleft()

        for adj in g[node]:
            if adj not in done:
                done.add(adj)
                q.append(adj)
                s.remove(adj)
    ans += 1

print(ans - 1)

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict

n, m = map(int, input().split())
g = defaultdict(list)
s = set(list(range(1, n+1)))
ans = 0

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

while s:
    root = s.pop()
    q = deque()
    q.append(root)
    done = set()
    done.add(root)
    while q:
        node = q.popleft()
        for adj in g[node]:
            if adj not in done:
                done.add(adj)
                q.append(adj)
                s.remove(adj)
    ans += 1

print(ans - 1)

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

num = L.count(1)
print(N-num)

Submission status: Runtime Error

Solution code:
class AlgUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  #各要素の親要素の番号を格納するリスト 要素が根（ルート）の場合は-(そのグループの要素数)を格納する

    def find(self, x): #要素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が属するグループと要素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): #要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y): #要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x): #要素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): #print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(M)]
    uf = AlgUnionFind(N)
    for i in range(M):
        uf.union(A[i][0], A[i][1])
    count = uf.group_count() - 1
    print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
Pajew = [i for i in range(n)]
import sys
sys.setrecursionlimit(1000000)

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

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

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

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

Submission status: 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())


import math


N, M = map(int, input().split())
uf = UnionFind(M)
for i in range(N):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)
x=uf.group_count()
print(x)
print(math.ceil(math.log(x,2)))

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict

n, m = map(int, input().split())
g = defaultdict(list)
s = set(list(range(1, n+1)))
ans = 0

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

while s:
    root = s.pop()
    q = deque()
    q.append(root)
    done = set()
    done.add(root)

    while q:
        node = q.popleft()

        for adj in g[node]:
            if adj not in done:
                done.add(adj)
                q.append(adj)
                s.remove(adj)
    ans += 1

print(ans - 1)

Submission status: Runtime Error

Solution code:
import sys
import math,bisect
sys.setrecursionlimit(10 ** 5)
from itertools import groupby,accumulate
from heapq import heapify,heappop,heappush
from collections import deque,Counter,defaultdict
def I(): return int(sys.stdin.readline())
def neo(): return map(int, sys.stdin.readline().split())
def Neo(): return list(map(int, sys.stdin.readline().split()))
class Graph:
    def __init__(self,V):
        self.V = V
        self.adj = [[] for i in range(V)]
    def DFSUtil(self, temp, v, visited):
        visited[v] = True
        temp.append(v)
        for i in self.adj[v]:
            if visited[i] == False:
                temp = self.DFSUtil(temp, i, visited)
        return temp
    def addEdge(self, v, w):
        self.adj[v].append(w)
        self.adj[w].append(v)
    def connectedComponents(self):
        visited = []
        cc = []
        for i in range(self.V):
            visited.append(False)
        for v in range(self.V):
            if visited[v] == False:
                temp = []
                cc.append(self.DFSUtil(temp, v, visited))
        return cc
N,M = neo()
G = Graph(N)
for i in range(M):
    x,y = neo()
    G.addEdge(x,y)
    G.addEdge(y,x)
print(len(G.connectedComponents())-1)

Submission status: Runtime Error

Solution code:
from collections import Counter
import string
import math
import sys
def array_int():
    return [int(i) for i in sys.stdin.readline().split()]
def vary(number_of_variables):
    if number_of_variables==1:
        return int(sys.stdin.readline())
    if number_of_variables>=2:
        return map(int,sys.stdin.readline().split()) 
def makedict(var):
    return dict(Counter(var))
mod=100000007
import math
fact=[1]
MAX=100001
mod=998244353
for i in range(1,MAX):
	fact.append((fact[-1]*i)%mod)
def ncr(n , k): 
    global mod,fact
    num=fact[n]
    den=((fact[n-k])*(fact[k]))%mod
    return (num*pow(den,mod-2,mod))%mod
n,m=vary(2)
visited=[0]*(n+1)
graph = [[] for i in range(n+1)]  

def dfs(node, parent): 
    global graph,visited
    visited[node]=1
    
    for to in graph[node]:  
        if (to == parent):  
            continue
        dfs(to, node)  

for i in range(m):
    u,v=vary(2)
    graph[u].append(v)
    graph[v].append(u)
count=0
for i in range(1,n+1):
    if visited[i]==0:
        dfs(i,i)
        count+=1
print(count-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 main():
    N, Q = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(Q):
        u, v = map(int, input().split())
        uf.union(u, v)
    print(uf.group_count()-1)   
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uni = UnionFind(n)
for i in range(m):
    a, b = ab[i]
    uni.union(a, b)
print(uni.group_count() - 1)

Submission status: Runtime Error

Solution code:
import math
n,m=map(int,input().split())
r=[0]*n
for i in range (m):
  a,b=map(int,input().split())
  r[a]+=1
  r[b]+=1
ma = max(r)
if ma>=n-1:
  print(0)
else:
  print(n-1-ma)

Submission status: Runtime Error

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

City_list = [[i] for i in range(N)]
ans = N - 1 - M

for i in range(M):
    Ai, Bi = map(int, input().split())

    if City_list[Ai] == City_list[Bi]:
        ans += 1
    else:
        City_list[Ai] = City_list[Ai] + City_list[Bi]
        City_list[Bi] = City_list[Ai]

print(ans)

Submission status: Runtime Error

Solution code:
# Python3 program to print DFS traversal
# from a given given graph
from collections import defaultdict

viz = [0]*1005
# This class represents a directed graph using
# adjacency list representation


class Graph:

    # Constructor
    def __init__(self):

        # default dictionary to store graph
        self.graph = defaultdict(list)

    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)

    # A function used by DFS
    def DFSUtil(self, v, visited):
        global viz
        # Mark the current node as visited
        # and print it
        visited[v] = True
        viz[v]=1
        # print(v, end=' ')

        # Recur for all the vertices
        # adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)

    # The function to do DFS traversal. It uses
    # recursive DFSUtil()
    def DFS(self, v,visited):

        # Mark all the vertices as not visited
        # visited = [False] * (max(self.graph)+1)

        # Call the recursive helper function
        # to print DFS traversal
        self.DFSUtil(v, visited)

        return visited

# Driver code


# Create a graph given
# in the above diagram

    
g = Graph()
n, m = map(int, input().split())
vizi=[False]*(n+1)
for i in range(m):
    a, b = map(int, input().split())
    g.addEdge(a, b)
    g.addEdge(b, a)

cnt = 0
vizi=g.DFS(0,vizi)
for i in range(1,n):
    if vizi[i] == False:
        cnt += 1
        vizi=g.DFS(i,vizi)

print(cnt)

# print("Following is DFS from (starting from vertex 2)")
# g.DFS(2)

# This code is contributed by Neelam Yadav

Submission status: Runtime Error

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

connect = {}
no_connection = [n + 1 for n in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  
  no_connection.remove(a)
  no_connection.remove(b)
  
  for group_idx, group_set in connect.items():
    if a in group_set:
      connect[group_idx] |= set([a, b])
      break
      
  else:
      connect[len(connect) + 1] = set([a, b])
      
print(len(connect) - 1 + len(no_connection))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
t=[]
for i in range(m):
    a=int(input())
    t.append(a)
l = len(set(t))
ans = n-l
print(ans)

Submission status: Runtime Error

Solution code:
# https://note.nkmk.me/python-union-find/
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 = list(map(int, input().split()))

uf = UnionFind(N)

for i in range(M):
    A, B = list(map(int, input().split()))
    uf.union(A,B)
    
print(uf.group_count()-1)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
M = [[0 for _ in range(n)] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    M[a][b] = 1
    
cnt = 0   
for i in range(n-1):
    if all(M[i][j] == 0 for j in range(1+i, n)):
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
from atcoder import dsu
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ds = dsu.DSU(n)
for i in ab:
    ds.merge(i[0]-1,i[1]-1)
    
s = ds.groups()
ans = 0
for i in s:
    if len(i)==1:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
# H4CKOM
N = int(100100)
g = [[] for i in range(N)]
vis = [False for i in range(N)]
vis2 = [False for i in range(N)]


def add_edge(u, v):
    g[u].append(v)


def dfs1(v):
    vis2[v] = True
    for to in g[v]:
        if not vis2[to]:
            dfs1(to)


def dfs2(v):
    global ans
    vis[v] = True
    ans += 1
    for to in g[v]:
        if not vis[to] and not vis2[to]:
            dfs2(to)


def get():
    global vis, ans
    dfs1(x)
    val = []
    for i in range(0, n):
        if not vis2[i]:
            ans = 0
            vis = [False for i in range(N)]
            dfs2(i)
            val.append((ans, i))
    val.sort(reverse=True)
    ans = 0
    for it in val:
        if not vis2[it[1]]:
            ans += 1
            dfs1(it[1])
    return ans


if __name__ == "__main__":

    n, x = map(int, input().split())
    for i in range(x):
        u, v = map(int, input().split())
        add_edge(u-1, v-1)
        add_edge(v-1, u-1)

    print(get())

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
group = []
tf = []
for i in range(M):
  A, B = map(int, input().split())
  if A and B not in tf:
    tf.append(A)
    tf.append(B)
    group.append([A,B])
  else:
    if A not in tf:
      tf.append(A)
      for j in range(len(group)):
        if B in group[j]:
          group[i].append(A)
          break
    else:
      tf.append(B)
      for j in range(len(group)):
        if A in group[j]:
          group[i].append(B)
          break
l = list(range(1,N+1))
for i in tf:
  if i in l:
    l.remove(i)
    
print(len(group)+len(l)-1)

Submission status: Runtime Error

Solution code:

def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

#bit = [i>>j&1 for j in range(n)]

n,m=MII()
connect_city=[LII() for _ in range(m)]
groups=[[1]]

for i in range(m):
    a,b=connect_city[i]
    flag=0
    for j,group in enumerate(groups):
        if a in group:
            groups[j]+=[b]
            flag=1
            continue
        elif b in group:
            groups[j]+=[a]
            flag=1
            continue
    if flag==0:
        groups+=[a,b]

for i in range(1,n+1):
    for group in groups:
        if i in group:
            continue
        else:
            groups+=[[i]]

print(len(groups)-1)

Submission status: Runtime Error

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

import sys
# from atcoder.dsu import DSU

sys.setrecursionlimit(10**6)

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

for _ in range(M):
    A, B = map(int, input().split())
    d.merge(A, B)

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
data=list(range(n))
cnt=n-1
def find(x):
    if data[x]==x:
        return x
    else:
        find(data[x])
for i in range(m):
    a,b=map(int,input().split())
    a=find(a-1)
    b=find(b-1)
    if a!=b:
        data[a]=b
        cnt-=1
print(cnt)

Submission status: Runtime Error

Solution code:
import collections
sys.setrecursionlimit(10**6)
def dfs(visited,v,adj):
    visited[v]=True 
    for i in adj[v]:
        if not visited[i]:
            dfs(visited,i,adj)  
adj=collections.defaultdict(list)
n,m=map(int,input().split()) 
visited=[False]*n  
for i in range(m):
    u,v=map(int,input().split()) 
    adj[u-1].append(v-1)  
    adj[v-1].append(u-1) 
c=0 
for i in range(n):
    if not visited[i]:
        dfs(visited,i,adj) 
        c+=1 
print(c-1)

Submission status: Runtime Error

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]
 
    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size
 
    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x
 
    def is_connected(self, x: int, y: int) -> bool:
        return self[x] == self[y]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x
 
 
import sys
 
readline = sys.stdin.readline
 
N, Q = map(int, readline().split())
tree = UnionFind(N)
res = []
ans=0
for _ in range(Q):
  u, v = map(int, readline().split())
  if not tree.unite(u, v):
    res.append(int(tree.is_connected(u, v)))
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
#c
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ds = dsu.DSU(n)
for i in ab:
    ds.merge(i[0]-1,i[1]-1)
    
s = ds.groups()
ans = 0
for i in s:
    if len(i)==1:
        ans+=1
print(ans)

Submission status: Runtime Error

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
import sys

def main():
  pin=sys.stdin.readline
  N,M=map(int,pin().split())
  uf=DSU(N)
  for i in range(M):
    A,B=map(int,pin().split())
    uf.merge(A,B)
  ans=len(uf.groups())
  print(ans-1)
  return
main()

Submission status: Runtime Error

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

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

for i in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    cur = par[b]
    par[b] = par[a]
    while(cur in par):
        idx = par.index(cur)
        par[idx] = par[a]

ans = len(set(par)) - 1
print(ans)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1000000)
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]

n, m = m_in(int)
ab = [list(m_in(int)) for _ in range(m)]

nodes = [i for i in range(n)]
for a, b in ab:
    nodes.pop(b-1)

ans = len(nodes)-1

print(ans)

Submission status: Runtime Error

Solution code:
import sys,io,os
I = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
I = input

n,m = map(int, I().split())
p=[-1]*(n+1)
s=[0]*(n+1)
S=n-1
def t(a):
	while p[a] != -1:
		a = p[a]
	return a
for _ in range(m):
	a,b=map(int, I().split())
	a,b = t(a), t(b)
	if a != b:
		S -= 1
		if s[a] > s[b]:
			a,b = b,a
		p[a] = b
		s[b] += s[a]
print(S)

Submission status: Runtime Error

Solution code:
def dfs(v):
    global visited
    visited[v] = True
    for nv in graph[v]:
        if nv in graph[v]:
            if not visited[nv]:
                dfs(nv)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    visited = [False]*N
    for _ in range(M):
        A, B = map(lambda x: int(x)-1, input().split())
        graph[A].append(B)
        graph[B].append(A)
    ans = -1
    for v in range(N):
        if not visited[v]:
            dfs(v)
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        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,b)
size = 0
for i in range(n):
    if uf.parents[i] == i:
        size += 1
print(size-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        self.d = []
        for _ in range(n):
            self.d.append(-1)
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x

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

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


N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    uf.union(a,b)
group = set()
for i in range(N):
    group.add(uf.find(i))

print(len(group)-1)