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 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)
G=[[] for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a,b)
  
print(uf.group_count()-1)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m=map(int,input().split())
road=[[] for i i range(n)]
flag=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)
count=0
for i in range(n):
    if flag[i]!=0:
        continue
    count+=1
    q=[k]
    while q:
        p=q.popleft()
        for z in road[p]:
            if flag[z]==0:
                q.append(z)
print(count-1)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
lst=[list(map(int, input().split()))]
town=[1]*n
for j in range(2):
        town[lst[0][j]-1]=0
l=1
for i in range(m-1):
    a=list(map(int, input().split()))
    for j in range(2):
        town[a[j]-1]=0
    cnt=0
    for k in range(l):
        if (a[0] or a[1]) in lst[k]:
            lst[k].append(a[0])
            lst[k].append(a[1])
            break
        else:
            cnt+=1
        if cnt==l:
            lst.append[a]
            l+=1
                
print(len(lst)+sum(town)-1)
#print(town,lst)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
L = [0] * N
D = {}
c = 1
for i in range(M):
  A, B = map(int, input().split())
  if L[A - 1] == L[B - 1] == 0:
    D[c] = set()
    D[c].add(A)
    D[c].add(B)
    L[A - 1] = c
    L[B - 1] = c
    c += 1
  elif L[A - 1] == 0:
    D[L[B - 1]].add(A)
    L[A - 1] = L[B - 1]
  elif L[B - 1] == 0:
    D[L[A - 1]].add(B)
    L[B - 1] = L[A - 1]
  elif L[A - 1] != L[B - 1]:
    D[L[A - 1]] |= D[L[B - 1]]
    for j in D.pop(L[B - 1]):
      L[j - 1] == L[A - 1]
  #print(L, D, sep = "\n")
print(len(D) + L.count(0) - 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:
N, M = map(int, input().split())
L = [0] * N
D = {}
c = 1
for i in range(M):
  A, B = map(int, input().split())
  if L[A - 1] == 0 and L[B - 1] == 0:
    D[c] = set()
    D[c].add(A)
    D[c].add(B)
    L[A - 1] = c
    L[B - 1] = c
    c += 1
  elif L[A - 1] == 0:
    D[L[B - 1]].add(A)
    L[A - 1] = L[B - 1]
  elif L[B - 1] == 0:
    D[L[A - 1]].add(B)
    L[B - 1] = L[A - 1]
  else:
    D[L[A - 1]] |= D[L[B - 1]]
    for j in D.pop(L[B - 1]):
      L[j - 1] == L[A - 1]
#print(L, D, sep = "\n")
print(len(D) + L.count(0) - 1)

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n, m = map(int, input().split())
uf = UnionFind(n)
 
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
print(uf.group_count()-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict 
class graph:
    def __init__(self,V):
        self.V=V
        self.graph=defaultdict(list)
    def dfs(self,temp,v,visited):
        visited[v]=True
        temp.append(v)
        for i in self.graph[v]:
            if visited[i]==False:
                temp=self.dfs(temp,i,visited)
        return temp
    def addEdge(self,v,w):
        self.graph[v].append(w)
        self.graph[w].append(v)
    def cnt(self):
        visited=[]
        cc=[]
        for i in range(self.V):
            visited.append(False)
        for i in range(self.V):
            if visited[i]==False:
                temp=[]
                cc.append(self.dfs(temp,i,visited))
        return cc
n,m=map(int,input().split())
g=graph(n)
for i in range(m):
    x,y=map(int,input().split())
    g.addEdge(x-1,y-1)
cc = g.cnt()
print(len(cc)-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict 
class graph:
    def __init__(self,V):
        self.V=V
        self.graph=defaultdict(list)
    def dfs(self,temp,v,visited):
        visited[v]=True
        temp.append(v)
        for i in self.graph[v]:
            if visited[i]==False:
                temp=self.dfs(temp,i,visited)
        return temp
    def addEdge(self,v,w):
        self.graph[v].append(w)
        self.graph[w].append(v)
    def cnt(self):
        visited=[]
        cc=[]
        for i in range(self.V):
            visited.append(False)
        for i in range(self.V):
            if visited[i]==False:
                temp=[]
                cc.append(self.dfs(temp,i,visited))
        return cc
n,m=map(int,input().split())
g=graph(n+1)
for i in range(m):
    x,y=map(int,input().split())
    g.addEdge(x,y)
cc = g.cnt()
print(len(cc)-2)

Submission status: Runtime Error

Solution code:
def s(way):
    global w
    global c
    for i in way:
        if c[i] == 0:
            c[i] = 1
            s(w[i])

from collections import deque

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

w = [[] for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    w[a-1].append(b-1)
    w[b-1].append(a-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        ans += 1
        s(w[i])
print(ans)

Submission status: Runtime Error

Solution code:
def s(way):
    global  w
    for i in way:
        if c[i] == 0:
            c[i] = 1
            s(w[i])

from collections import deque

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

w = [[] for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    w[a-1].append(b-1)
    w[b-1].append(a-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        ans += 1
        s(w[i])
print(ans)

Submission status: Runtime Error

Solution code:
def s(way):
    global  w
    for i in way:
        if c[i] == 0:
            c[i] = 1
            s(w[i])

from collections import deque

d = deque()
n,m = map(int,input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
w = [[] for i in range(n)]
wc = [0 for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    w[a[i]-1].append(b[i]-1)
    w[b[i]-1].append(a[i]-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        ans += 1
        s(w[i])
print(ans)

Submission status: Runtime Error

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,m=input2()
AB=[input_array() for _ in range(m)]


uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict 
class graph:
    def __init__(self,V):
        self.V=V
        self.graph=defaultdict(list)
    def dfs(self,temp,v,visited):
        visited[v]=True
        temp.append(v)
        for i in self.graph[v]:
            if visited[i]==False:
                temp=self.dfs(temp,i,visited)
        return temp
    def addEdge(self,v,w):
        self.graph[v].append(w)
        self.graph[w].append(v)
    def cnt(self):
        visited=[]
        cc=[]
        for i in range(self.V):
            visited.append(False)
        for i in range(self.V):
            if visited[i]==False:
                temp=[]
                cc.append(self.dfs(temp,i,visited))
        return cc
n,m=map(int,input().split())
g=graph(n)
for i in range(m):
    x,y=map(int,input().split())
    g.addEdge(x,y)
cc = g.cnt()
print(len(cc)-1)

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, n):
    self.class = [i for i in range(n)]
    self.n = n
  def whichclass(self, x):
    if self.class[x]==x:
      return x
    else:
      self.class[x] = self.whichclass(self.class[x])
      return self.class[x]
  def union(self, x, y):
    cx = self.whichclass(x)
    cy = self.whichclass(y)
    if cx==cy:
      return
    minc = min(cx, cy)
    maxc = max(cx, cy)
    self.class[maxc] = minc
  def __getitem__(self, x):
    return self.whichclass(x)
  
N, M = map(int, input().split())
UF = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  UF.union(a, b)
count = [0 for i in range(N)]
for i in range(N):
  count[UF[i]] = 1
print(sum(count)-1)

Submission status: Runtime Error

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

l.sort()
a =[[l[0][0],l[0][1]]]
cnt = 0
num = 1
for i in range(1, m):
    if l[i][0] in a[cnt] and l[i][1] not in a[cnt]:
        a[cnt].append(l[i][1])
        num += 1
    elif l[i][1] in a[cnt] and l[i][0] not in a[cnt]:
        a[cnt].append(l[i][0])
        num += 1
    else:
        cnt += 1



print(n- num -1)

Submission status: Runtime Error

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
    # ノードxのrootノードを見つける
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
    # 木の併合、入力は併合したい各ノード⇒(a,b)
        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())

uni = UnionFind(n)
for i in range(m):
    a,b = map(int, input().split())
    uni.unite(a-1, b-1)

cnt = [0]*(n)
for aa in uni.par:
    cnt[aa] = 1

print(sum(cnt)-1)

Submission status: Runtime Error

Solution code:
import numpy as np
n, m =list(map(int,input().split()))
x=np.array([list(map(int,input().split())) for i in range(m)])


data=x
ans=0
add_times = len(np.arange(1,n+1))-len(np.unique(np.array(x)))

while(1):
    if len(data)==0:
        break
    num=[data[0][0]]
    data =check_cl(data,num)
    ans+=1

print(int(ans-1+add_times))

Submission status: Runtime Error

Solution code:
import os
import sys
from io import BytesIO, IOBase



def main():
    # sys.setrecursionlimit(10**6)
    n, m = getints()
    g = [-1] * n
    def find(u):
        if g[u] < 0:
            return u
        else:
            g[u] = find(u)
            return g[u]
    def merge(u, v):
        u = find(u)
        v = find(v)
        if u != v:
            g[u] += g[v]
            g[v] = u
    for _ in range(m):
        a, b = getints()
        merge(a - 1, b - 1)
    cnt = 0
    for i in g:
        if i < 0:
            cnt += 1
    print(cnt - 1)


# region fastio


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input(): return sys.stdin.readline().rstrip("\r\n")
def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint1(): return list(map(lambda x: int(x) - 1, input().split()))


# endregion


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    roads=[]
    n,m = map(int,input().split())
    roads=[list(map(int,input().split())) for _ in range(m)]
    count=0

    for i in range(1,n+1):
        if roads in i:
            continue
        else:
            count+=1
    print(count)

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
count = 0
t = 1

for t in range(N):
    A,B = map(int,input().split())
   
    if  t == A or t == B:
        count += 0
        
    else:
        count += 1 
       
            
print(count)

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())
V, E = map(int, input().split())
edges = []
for i in range(E):
    w = 1
    s, t = map(int, input().split())
    edges.append((w, s-1, t-1))
edges.sort()

def kruskal(n, edges):#edges: wでソート済み
    U = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not U.same(s, t):
            res+=w
            U.unite(s, t)
    return res
print(kruskal(V, edges))

Submission status: Runtime Error

Solution code:
from math import factorial


def main():
    n, m = map(int, input().split())
    a = [0] * m
    b = [0] * m
    c = [0] * n
    
    for i in range(m):
        a[i], b[i] = map(int, input().split())
        c[a[i]] = 1
        c[b[i]] = 1



    sum = factorial(n) / 2 * factorial(n - 2)
    if sum <= m:
        print(0)
        exit()

    count = 0
    for i in range(n):
        if c[i] == 0:
            count += 1

    print(count)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))

N = a[0]
M = a[1]

cities = [0] * N
roads = []

lands = {}
for i in range(M):
    a = list(map(int,input().split()))
    roads.append([a[0], a[1]])

for r in roads:
    #print(cities)
    #print(lands)
    if cities[r[0]-1] == 0:
        cities[r[0]-1] = r[0]
        lands[cities[r[0]-1]] = [r[0]]
    
    if cities[r[1]-1] == 0:
        cities[r[1]-1] = r[0]
        lands[cities[r[0]-1]].append(r[1])
    else:
        #print(cities[r[1]-1])
        #print(cities[r[1]-1] in lands)
        td_idx = cities[r[1]-1]
        if cities[r[1]-1] in lands:
            lands[cities[r[0]-1]].extend(lands[cities[r[1]-1]])
            
            for i in range(len(lands[cities[r[1]-1]])):
                cities[lands[cities[r[1]-1]][i]] = cities[r[0]-1]
            del lands[td_idx]
        #else:
        #    cities[r[1]-1] = r[0]
        #    lands[r[0]-1].append()


#print(cities)
#print(cities)
#print(lands)
found = {}
zero_count = 0
for i in range(N):
    if cities[i] != 0:
        found[cities[i]] = 1
    else:
        zero_count += 1

print(len(found) - 1 + zero_count)

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
a=[list(map(int,input().split())) for l in range(y)]
M=0
c=0
t=[]
g=[]
g.append(a[0][0])
g.append(a[1][0])
while M<y-1:
    if not a[0][M] in t:
        t.append(a[0][M])
        if not a[1][M] in t:
            t.append(a[1][M])
            c=c+3
            
    if a[0][M] in t:
        if a[1][M] in t:
            g.append(a[0][M])
            g.append(a[0][M])
            if not a[0][M] in g:
              if not a[1][M] in g:
                c=c-1
            else:
              t.append(a[0][M])
              t.append(a[1][M])
              
              
           
    M=M+1


print(c-1)

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10000)

class UnionFindTree:
	def __init__(self,size):
		"""
		size個の集合を作成
		負の値は、ルートで集合の個数
		正の値は、次の要素
		"""
		self.table=[-1 for _ in range(size)]

	def find(self,x):
		"""
		グループ番号を取得
		"""
		# 本質的には、木を上に辿るだけ
		# ただし、通常、UnionFindでは経路圧縮を行うのが普通らしい
		if self.table[x] < 0:
			# 一個上がルートならば、それを返して終わり
			return x
		else:
			# そうでなければ、ルートまで辿るついでに経路圧縮
			self.table[x] = self.find(self.table[x])
			return self.table[x]
		return x

	# 併合
	def union(self,x,y):
		# s1,s2は正
		# table[s1],table[s2]は負
		s1=self.find(x)
		s2=self.find(y)
		if s1!=s2:
			# 個数が小さい方をルートにくっつける
			# ルートサイズは負なので、ルートが大きい方が個数が小さい?
			if self.table[s2]<=self.table[s1]:
				# s1が小さい
				self.table[s1]+=self.table[s2]
				self.table[s2]=s1
			else:
				# s2が小さい
				self.table[s2]+=self.table[s1]
				self.table[s1]=s2
			return True
		return False

	def groupCount(self):
		ret=0
		for i in range(len(self.table)):
			if self.table[i] < 0:
				ret+=1
		return ret

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

UF=UnionFindTree(N)

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


print(UF.groupCount()-1)

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
for i in range(M):
    A[i] , B[i] = map(int, input().split())

uf = UnionFind(N)
for i in range(M):
    uf.union(A[i], B[i])
print(uf.group_count()-1)

Submission status: Runtime Error

Solution code:
def dfs(now_node):
    seen[now_node] = True
    connect_nodes = graph[now_node]
    for node in connect_nodes:
        if seen[node] == True:#探索済みだったらスルー
            continue
        dfs(node)

N, M = map(int, input().split())
#edges = [list(map(int, input().split())) for i in range(M)]
edges = []
for i in range(M):
    edges.append(list(map(int, input().split())))

graph = [[] for i in range(N+1)]
#隣接リストの作成
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])
#訪問済みリストの作成
seen = [False for i in range(N+1)]
seen[0] = True
#全ノードが訪問済みになるまで探索
count = 0
for i in range(1, N+1):
    if seen[i]:#探索済みだったらスルー
        continue
    dfs(i)
    count += 1

print(count-1)

Submission status: Runtime Error

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

for i in range(M):
  temp=list(map(lambda x: x-1, map(int, input().split(" "))))
  graph[temp[0]].append(temp[1])
  graph[temp[1]].append(temp[0])

# print(graph)
seen=[False for i in range(N)]
todo=[]

def seek(graph, current):
  seen[current]=True
  for city in graph[current]:
    if seen[city]:
      continue
    seek(graph, city)

seek(graph, 0)
# print(seen)
candidate=[i for i in range(len(seen)) if seen[i]==False]
# print(candidate)
count=0
for i in candidate:
  graph[0].append(i)
  # print('append', graph)
  count=count+1
  seek(graph, 0)
  # print('appendseen', seen)
  if seen.count(False)==0:
    break
print(count)

Submission status: Runtime Error

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

# 島つくる
for i in range(m):
    for j in range(i+1,m):
        if brdg[i][0] in brdg[j]:
            brdg.append(list(set(brdg[i]+brdg[j])))
            brdg.remove(brdg[i])
            brdg.remove(brdg[j])
        if brdg[i][1] in brdg[j]:
            brdg.append(list(set(brdg[i]+brdg[j])))
            brdg.remove(brdg[i])
            brdg.remove(brdg[j])
            
# ないやつ孤島で足す
ans = 0
for k in range(1,n+1):
    flag = True
    for bg in brdg:
        if k in bg:
            flag = False
    if flag:
        ans += 1

print(n - (ans + len(brdg)))

Submission status: Runtime Error

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

for i in range(M):
  temp=list(map(lambda x: x-1, map(int, input().split(" "))))
  graph[temp[0]].append(temp[1])
  graph[temp[1]].append(temp[0])

print(graph)
seen=[False for i in range(N)]
todo=[]

def seek(graph, current):
  seen[current]=True
  for city in graph[current]:
    if seen[city]:
      continue
    seek(graph, city)

seek(graph, 0)
print(seen)
candidate=[i for i in range(len(seen)) if seen[i]==False]
print(candidate)
count=0
for i in candidate:
  graph[0].append(i)
  print('append', graph)
  count=count+1
  seek(graph, 0)
  print('appendseen', seen)
  if seen.count(False)==0:
    break
print(count)

Submission status: Runtime Error

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

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

for i in range(m):
    a, b = map(int, input().split())
    cur = connection[b]
    connection[b] = connection[a]
    par[cur] = par[a]
for i in range(n):
    num = connection[i]
    connection[i] = par[num]
ans = len(set(connection)) - 1
print(ans)

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.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
#a = [i+1 for i in range(n)]
d = Unionfind(n)

for i in range(m):
    a,b = map(int,input().split())
    d.union(a,b)
max1 = 0
for i in range(n):
    max1 = max(max1,d.size(i))
print(max1-1)

Submission status: Runtime Error

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

f = [[]]
cnt=0

for i in range(m):
    flg=0
    for j in range(cnt):
        if a[i] in f[j]:
            f[j].append(b[i])
            flg = 1
        elif b[i] in f[j]:
            f[j].append(a[i])
            flg = 1
    if flg != 1:
        f[cnt].append(a[i])
        f[cnt].append(b[i])
        cnt+=1

print(cnt)

Submission status: Runtime Error

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

rootedPoints = set()
points = []

for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  rootedPoints.add(A)
  rootedPoints.add(B)
  Aindex = False
  Bindex = False
  for i, ps in enumerate(points):
    if A in ps: Aindex = i
    if B in ps: Bindex = i
    if Aindex is not False and Bindex is not False: break
  if Aindex is False and Bindex is False:
    points.append({A, B})
  elif Aindex is False:
    points[Bindex].add(A)
  elif Bindex is False:
    points[Aindex].add(B)
  elif Aindex!=Bindex:
    points[Aindex] |= points[Bindex]
    points[Bindex] = False
  #print(points)
print(len(tuple(pp for pp in points if pp!=False))-1+N-len(rootedPoints))

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))

N = a[0]
M = a[1]

cities = [0] * N
roads = []

lands = {}
for i in range(M):
    a = list(map(int,input().split()))
    roads.append([a[0], a[1]])

for r in roads:
    #print(cities)
    #print(lands)
    if cities[r[0]-1] == 0:
        cities[r[0]-1] = r[0]
        lands[r[0]] = [r[0]]
    
    if cities[r[1]-1] == 0:
        cities[r[1]-1] = r[0]
        lands[r[0]].append(r[1])
    else:
        #print(cities[r[1]-1])
        #print(cities[r[1]-1] in lands)
        td_idx = cities[r[1]-1]
        if cities[r[1]-1] in lands:
            lands[cities[r[0]-1]].extend(lands[cities[r[1]-1]])
            
            for i in range(len(lands[cities[r[1]-1]])):
                cities[lands[cities[r[1]-1]][i]] = cities[r[0]-1]
            del lands[td_idx]
        #else:
        #    cities[r[1]-1] = r[0]
        #    lands[r[0]-1].append()


#print(cities)
#print(cities)
#print(lands)
found = {}
zero_count = 0
for i in range(N):
    if cities[i] != 0:
        found[cities[i]] = 1
    else:
        zero_count += 1

print(len(found) - 1 + zero_count)

Submission status: Runtime Error

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

# 島つくる
for i in range(m):
    for j in range(i+1,m):
        if brdg[i][0] in brdg[j]:
            brdg.append(list(set(brdg[i]+brdg[j])))
            brdg.remove(brdg[i])
            brdg.remove(brdg[j])
        if brdg[i][1] in brdg[j]:
            brdg.append(list(set(brdg[i]+brdg[j])))
            brdg.remove(brdg[i])
            brdg.remove(brdg[j])
            
# ないやつ孤島で足す
ans = 0
for k in range(1,n+1):
    flag = True
    for bg in brdg:
        if k in bg:
            flag = False
    if flag:
        ans += 1

print(ans + len(brdg))