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:
n,m = list(map(int,input().split()))
c = []
cn = []
for _ in range(m):
  i,j = list(map(int,input().split()))
  if (not i in c) and (not j in c):
    c+=[i,j]
    cn.append([i,j])
  elif (not i in c):
    c.append(i)
    for a,x in enumerate(cn):
      if j in x:
        cn[a].append(i)
  elif (not j in c):
    c.append(j)
    for a,x in enumerate(cn):
      if i in x:
        cn[a].append(j)
  else:
    p = None
    idx = None
    for a,x in enumerate(cn):
      if i in x:
        if j in x:
          break
      if p == None:
        idx = a
        p = x
      else:
        cn.pop(idx)
        cn.pop(a)
        cn.append(x+p)
print(n-1-len(c)+len(cn))

Submission status: Runtime Error

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

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

for i in range(m):
    a,b=MII()
    flag=0
    if a in group_set:
        for group in groups:
            if a in group:
                group+=[b]
                group_set.add(b)
                #city_count+=1
                #flag=1
                continue
    elif b in group_set:
        for group in groups:
            if b in group:
                group+=[a]
                group_set.add(a)
                #city_count+=1
                #flag=1
                continue
    else:
        groups+=[a,b]
        group_set.add(a,b)
        #city_count+=2

print(len(groups)+(n-len(group_set))-1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(M)]

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

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

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

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

for a, b in ABs:
    unite(a-1, b-1)

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

Submission status: Runtime Error

Solution code:
class UnionFind:
  par = None
  
  def __init__(self, N):
    self.par = list(range(N))
    
  def root(self, x):
    if(self.par[x] == x):
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    if(self.root(x) != self.root(y)):
      self.par[x] = self.root(y)
  
N, M = list(map(int, input().split()))
UF = UnionFind(N)
for i in range(M):
  print(UF.par)
  A, B = list(map(int, input().split()))
  UF.unite(A - 1, B - 1) 
ans = 0
for i in range(N):
  ans += (UF.par[i] == i)
print(UF.par)
print(ans - 1)

Submission status: Runtime Error

Solution code:
class Vertex(object):
    def __init__(self, id):
        self.id = id
        self.adjacent = {}
        # DFS
        self.visited = False
    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight
    
    def get_neighbors(self):
        return self.adjacent
    def get_connections(self):
        return self.adjacent.keys()  
    def get_vertex_id(self):
        return self.id
    def get_weight(self, neighbor):
        return self.adjacent[neighbor]
    # DFS
    def set_visited(self):
        self.visited = True
class Graph(object):
    def __init__(self):
        self.vertex_dict = {}
        self.num_vertex = 0
    
    # DFS ループで扱いやすくする。
    def __iter__(self):
        return iter(self.vertex_dict.values())
    def add_vertex(self, id):
        self.num_vertex = self.num_vertex + 1
        new_vertex = Vertex(id)
        self.vertex_dict[id] = new_vertex
        return new_vertex
    def get_vertex(self, id):
        if id in self.vertex_dict:
            return self.vertex_dict[id]
        else:
            return None
    def add_edge(self, frm, to, weight=0):
        if frm not in self.vertex_dict:
            self.add_vertex(frm)
        if to not in self.vertex_dict:
            self.add_vertex(to)
        self.vertex_dict[frm].add_neighbor(self.vertex_dict[to], weight)
        # 有向グラフの場合は別
        self.vertex_dict[to].add_neighbor(self.vertex_dict[frm], weight)
    def get_vertices(self):
        return self.vertex_dict.keys()
    def get_edges(self):
        edges = []
        for v in self.vertex_dict.values():
            for w in v.get_connections():
                vid = v.get_vertex_id()
                wid = w.get_vertex_id()
                edges.append((vid, wid, v.get_weight(w)))
        return edges
def dfs(graph, current_vertex, traversal_verticies):
    current_vertex.set_visited()
    traversal_verticies.append(current_vertex.get_vertex_id())
    for neighbor in current_vertex.get_connections(): 
        if not(neighbor.visited):  
            dfs(graph, neighbor, traversal_verticies) 
 
def dfs_traversal(graph):
    n = 0
    for current_vertex in graph:
        traversal_verticies = []
        if not(current_vertex.visited):  
            dfs(graph, current_vertex, traversal_verticies) 
        if traversal_verticies:
            n += 1
    
    print(n - 1)
    
if __name__ == '__main__':
    graph = Graph()
    N, M = (int(i) for i in input().split())
    for i in range(N):
        graph.add_vertex(i+1)
    
    for i in range(M):
        a, b = (int(i) for i in input().split())
        graph.add_edge(a, b)
        
    dfs_traversal(graph)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
AB=list()
memo=[False]*N
G=dict()
def dfs(G,i):
    memo[i]=True
    for j in G[i]:
        if memo[j]==False:
            G.setdefault(j,[])
            dfs(G,j)
count=0
for i in range(M):
    AB=list(map(int,input().split()))
    G.setdefault(AB[0]-1,list())
    G.setdefault(AB[1]-1,list())
    G[AB[1]-1].append(AB[0]-1)
    G[AB[0]-1].append(AB[1]-1)
for i in range(N):
    if memo[i]==False:
        G.setdefault(i,[])
        dfs(G,i)
        count+=1
print(count-1)

Submission status: Runtime Error

Solution code:
def main(dic,lst):
  seen =set()
  res = 0
  def bfs(i):
    if i in seen:
      return
    seen.add(i)
    for j in dic[i]:
      bfs(j)
  
  for i in lst:
    if i in seen:
      continue
    bfs(i)
    res+=1
  return res-1
n, m = tuple(map(int, input().split()))
lst = [i for i in range(1,n+1)]
from collections import defaultdict
dic = defaultdict(list)
for i in range(m):
  o,p = tuple(map(int,input().split()))
  dic[o].append(p)
  dic[p].append(o)
print(main(dic,lst))

Submission status: Runtime Error

Solution code:
def dfs(now, prev):
    global flag
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]:
                # 過去に訪れていれば閉路
                flag = False
            else:
                memo[next] = True
                dfs(next, now)


n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

# 訪れたことがあるか
memo = [False for i in range(n)]

ans = 0
# 頂点をループ
for i in range(n):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        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())
n = list(i+1 for i in range(N))
count = 0

for _ in range(M):
    A, B = map(int, input().split())
    if A in n or B in n:
        count+=1
        n[A] = 0
        n[B] = 0

print(N-1-count)

Submission status: Runtime Error

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

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(N)
#print(uf.parents)

for i in range(M):
    a = list(map(int, input().split()))
    uf.union(a[0], a[1])

print(uf.group_count()-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:
  	ans += 1
    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)
print(ans - 1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
fathers = {t:t for t in range(n)}
cnt = 0
def get_father(n) :
    while not fathers[n] == fathers[fathers[n]] :
        fathers[n] = fathers[fathers[n]]
    return fathers[n]
for i in range(m):
    ai, bi = map(int, input().split())
    if get_father(ai) == get_father(bi):
        continue
    fathers[get_father(bi)] = get_father(ai)
flag = set()
for i in range(n):
    flag.add(fathers[i])
print(len(flag)-1)

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
c = []
cn = []
for _ in range(m):
  i,j = list(map(int,input().split()))
  if (not i in c) and (not j in c):
    c+=[i,j]
    cn.append([i,j])
  elif (not i in c):
    c.append(i)
    for a,x in enumerate(cn):
      if j in x:
        cn[a].append(i)
  elif (not j in c):
    c.append(j)
    for a,x in enumerate(cn):
      if i in x:
        cn[a].append(j)
  else:
    p = None
    for x in cn:
      if i in x:
        if j in x:
          break
      if p == None:
        p = x
      else:
        cn.remove(x)
        cn.remove(p)
        cn.append(x+p)
print(n-1-len(c)+len(cn))

Submission status: Runtime Error

Solution code:
n,m=int(input()),int(input())
a,b=input(input()),input(input())
if a: print(n-m-1)
else:print(n-m)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
L = [list(map(int,input().split())) for i in range(m)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

    def group_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.parent) if i == x]

    def group_count(self):  # 木の数を返す
        return len(self.roots())

    def all_group_members(self):  # すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}

#a = [i+1 for i in range(n)]
d = UnionFind(n)

for i in range(m):
    d.unite(L[i][0],L[i][1])

print(n-d.group_count())

Submission status: Runtime Error

Solution code:
n,m=int(input()),int(input())
a,b=int(input()),int(input())
if a: print(n-2)
else:print(n-1)

Submission status: Runtime Error

Solution code:
def dfs(now, prev):
    global flag
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]:
                # 過去に訪れていれば閉路
                flag = False
            else:
                memo[next] = True
                dfs(next, now)

N, M = map(int, input().split())
g = [[] * N for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    g[A].append(B)
    g[B].append(A)

# 訪れたことがあるか
memo = [False for i in range(N)]
ans = 0
# 頂点をループ
for i in range(N):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        ans += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
def Search(pos):
  L[pos-1] = 1
  if pos not in R:
    R[pos] = set()
    R[pos].add(1)
    return
  for i in R[pos]:
    if L[i-1] == 0:
      Search(i)

N, M = map(int, input().split())
R = {}
for i in range(M):
  A, B = map(int, input().split())
  if A not in R:
    R[A] = set()
  if B not in R:
    R[B] = set()
  R[A].add(B)
  R[B].add(A)
L = [0] * N
ans = -1
while sum(L) < N:
  ans += 1
  Search(L.index(0) + 1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = 10**5+1
g = [[] for i in range(N)]

vis = [False for i in range(N)]

good = [False for i in range(N)] 
  
def ADD_EDGE(u, v): 
    g[u].append(v)
    
def dfs1(v): 
    good[v] = True
    for to in g[v]: 
        if not good[to]: 
            dfs1(to)
            
def dfs2(v):
    global cnt 
    vis[v] = True
    cnt += 1
    for to in g[v]: 
        if not vis[to] and not good[to]: 
            dfs2(to)
            
def Minimum_Edges():
    global vis, cnt
    dfs1(x)
    
    val = [] 
  
    for i in range(0, n):
        if not good[i]: 
            cnt = 0
            vis = [False for i in range(N)]
            
            dfs2(i) 
            val.append((cnt, i))
            
    val.sort(reverse = True)
    
    ans = 0
    for it in val:  
        if not good[it[1]]:  
            ans += 1
            dfs1(it[1]) 
  
    return ans



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

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

x = 2*m

print(Minimum_Edges())

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
for i in range(N) :
    A,B = map(int,input().split())
    
print(N-1-M)

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(m)]

*p, = range(n)
rank = [1]*n
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1
 
for a,b in ab:
    unite(a,b)

print( len(set(p)) - 1 )

Submission status: Runtime Error

Solution code:
from collections import Counter
import string
import math
import sys
sys.setrecursionlimit(10**6) 
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:
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

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

for i in range(m):
    a,b=MII()
    flag=0
    for group in groups:
        if a in group:
            group+=[b]
            city_count+=1
            flag=1
            continue
        elif b in group:
            group+=[a]
            city_count+=1
            flag=1
            continue
    if flag==0:
        groups+=[a,b]
        city_count+=2

print(len(groups)+(n-city_count)-1)

Submission status: Runtime Error

Solution code:
N = 10**5+1
g = [[] for i in range(N)]

vis = [False for i in range(N)]

good = [False for i in range(N)] 
  
def ADD_EDGE(u, v): 
    g[u].append(v)
    
def dfs1(v): 
    good[v] = True
    for to in g[v]: 
        if not good[to]: 
            dfs1(to)
            
def dfs2(v):
    global cnt 
    vis[v] = True
    cnt += 1
    for to in g[v]: 
        if not vis[to] and not good[to]: 
            dfs2(to)
            
def Minimum_Edges():
    global vis, cnt
    dfs1(x)
    
    val = [] 
  
    for i in range(0, n):
        if not good[i]: 
            cnt = 0
            vis = [False for i in range(N)]
            
            dfs2(i) 
            val.append((cnt, i))
            
    val.sort(reverse = True)
    
    ans = 0
    for it in val:  
        if not good[it[1]]:  
            ans += 1
            dfs1(it[1]) 
  
    return ans



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

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

x = 2*m

print(Minimum_Edges())

Submission status: Runtime Error

Solution code:
import sys


def dfs(idx):
    for x in arr[idx]:
        if not vis[x]:
            vis[x] = True
            dfs(x)


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

arr = [[] * (n + 1) for _ in range(n + 1)]
vis = [False] * (n + 1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)

ans = 0

dfs(1)
for i in range(2, n + 1):
    if not vis[i]:
        vis[i] = True
        dfs(i)
        ans += 1
for i in range(1, n + 1):
    if not vis[i]:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split( ))
loads = []
teams = [[i] for i in range(N)]
syozoku = {i:i for i in range(N)}
for _ in range(M):
    A,B = map(int,input().split( ))
    if syozoku[A-1] != syozoku[B-1]:
        hairu,nukeru = min(syozoku[A-1],syozoku[B-1]),max(syozoku[A-1],syozoku[B-1])
        team = teams.pop(nukeru)
        teams[hairu] += team
        for i in team:
            syozoku[i] = hairu
ans = len(teams) - 1
print(ans)

Submission status: Runtime Error

Solution code:
'''
Created on 2020/09/26

@author: harurun
'''
#UnionFind(要素数)で初期化
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        #parents 各要素の親番号を格納するリストを返す

    #要素xが属するグループを返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    #要素xとyが属するグループを併合する
    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

    #要素xが属するグループのサイズ
    def size(self, x):
        return -self.parents[self.find(x)]

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

    #要素xが属するグループを返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    #すべての根の要素
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    #グループの数
    def group_count(self):
        return len(self.roots())

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N,M=map(int,pin().split())
  ans=0
  uf=UnionFind(N)
  for i in range(M):
    A,B=map(int,pin().split())
    if uf.same(A,B):
      continue
    uf.union(A, B)
  print(uf.group_count()-1)
  return 
main()

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:
        return 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:
# 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(1,vizi)
for i in range(2,n+1):
    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 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:
N = 10**5
g = [[] for i in range(N)]

vis = [False for i in range(N)]

good = [False for i in range(N)] 
  
def ADD_EDGE(u, v): 
    g[u].append(v)
    
def dfs1(v): 
    good[v] = True
    for to in g[v]: 
        if not good[to]: 
            dfs1(to)
            
def dfs2(v):
    global cnt 
    vis[v] = True
    cnt += 1
    for to in g[v]: 
        if not vis[to] and not good[to]: 
            dfs2(to)
            
def Minimum_Edges():
    global vis, cnt
    dfs1(x)
    
    val = [] 
  
    for i in range(0, n):
        if not good[i]: 
            cnt = 0
            vis = [False for i in range(N)]
            
            dfs2(i) 
            val.append((cnt, i))
            
    val.sort(reverse = True)
    
    ans = 0
    for it in val:  
        if not good[it[1]]:  
            ans += 1
            dfs1(it[1]) 
  
    return ans



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

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

print(Minimum_Edges())

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
L = [list(map(int,input().split())) for i in range(m)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

    def group_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.parent) if i == x]

    def group_count(self):  # 木の数を返す
        return len(self.roots())

    def all_group_members(self):  # すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}

#a = [i+1 for i in range(n)]
d = UnionFind(n)

for i in range(m):
    d.unite(L[i][0],L[i][1])
ans = 10**32
for i in range(n):
    ans = min(ans,n-d.group_size(i))
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(100001)]
    mark=[0]*N
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A-1].append(B-1)
        dic[B-1].append(A-1)
    
    def dfs(idx):
        if mark[idx]:
            return
        mark[idx]=1
        for a in dic[idx]:
            dfs(a)

    i=0
    count=0
    while True:
        if not mark[i]:
            count+=1
            dfs(i)
        i+=1
        if i==N:
            break
    
    print(count-1)
main()

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**9)

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)