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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, M = MI()
    used = [1] * N
    for i in range(M):
        a, b = MI1()
        used[a] = 0
        used[b] = 0
    print(sum(used))
    
        
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# 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?

# Solution:
#   Each road either: creates a new group; extends an existing one; or merges two
#     existing groups.
#   Use array GROUP to track the group of each city, all set to None initially.
#   Each group has a PARENT. A new group is created when two groups are merged, and
#     each group points to the new one as its parent. The new group has no parent (None).
#   After processing all roads: count the unique groups (i.e. groups with no parent) and
#     the cities with no group (i.e. they have no road).
#   If there are 6 unique groups, then 5 roads will ensure they are all connected.
#   If there are 4 Nones, then 4 roads are needed to connect them to groups.
#   Answer = (#groups - 1) + #Nones

def count(gen):
    n = 0
    for x in gen:
        if x:
            n += 1
    return n

# Read N (number of cities) and M (number of roads).
N, M = [int(x) for x in input().split()]
# Initialize GROUP and PARENT.
GROUP = [None for _ in range(N+1)]
PARENT = dict()
# G is the most recent group number. Increment before assigning a new group.
G = 0

# Process each road.
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    #print(f"road: {a} {b}")
    if GROUP[a] and GROUP[b]:
        if GROUP[a] == GROUP[b]:
            # The road is simply reinforcing an existing group. No action required.
            continue
        else:
            # We have a merger.
            G += 1
            ##print(f"  merger - groups {GROUP[a]} and {GROUP[b]} --> {G}")
            PARENT[G] = None
            PARENT[GROUP[a]] = G
            PARENT[GROUP[b]] = G
            GROUP[a] = G
            GROUP[b] = G
    elif GROUP[a]:
        # Extend existing group.
        GROUP[b] = GROUP[a]
        ##print(f"  extend group {GROUP[a]}")
    elif GROUP[b]:
        # Extend existing group.
        GROUP[a] = GROUP[b]
        ##print(f"  extend group {GROUP[b]}")
    else:
        # Neither has a group; we start a new one.
        G += 1
        ##print(f"  new group {G}")
        PARENT[G] = None
        GROUP[a] = G
        GROUP[b] = G

##print()
##print(GROUP)
##print(PARENT)

# Count the unique groups and the isolated cities.
num_groups   = count(PARENT[x] is None for x in range(1, G+1))
num_isolated = count(GROUP[x]  is None for x in range(1, N+1))

##print(num_groups, num_isolated)

# Get the answer.
answer = (num_groups - 1) + num_isolated

print(answer)

Submission status: Wrong Answer

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n = n
    self.parents = [-1] * (n+1)
  
  def find(self, x):
    if self.parents[x] < 0:
      return x
    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 -1 * self.parents[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()) - 1
  
N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
  a,b = map(int, input().split())
  uf.union(a,b)
ans = N - uf.group_count()
print(ans)

Submission status: Wrong Answer

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        tank = []
        while par[x] >= 0:
            tank.append(x)
            x = par[x]
        for elt in tank:
            par[elt] = x
        return x
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#集合の数
def numb():
    l = len(par)
    num = 0
    for ij in range(l):
        if par[ij] < 0:
            num += 1
    return num

n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))
par = [-1]*(n+1)
for j in range(m):
    unite(ab[j][0], ab[j][1])
print(par)
print(numb() - 2)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lN = [0] * (N + 1)
for m in range(M):
  for ab in list(map(int,input().split())):
    lN[ab] = 1
print(N - sum(lN))

Submission status: Wrong Answer

Solution code:
import numpy as np

N,M  = map(int,input().split())
Nlist = np.zeros(N,int)

muda = 0
for i in range(M):
  A,B  = map(int,input().split())
  if Nlist[A-1] == 1 and Nlist[B-1] == 1:
    muda += 1
  else:
    Nlist[A-1] = 1
    Nlist[B-1] = 1
ans = (N-1) - (M-muda)
print(ans)

Submission status: Wrong Answer

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

for i in range(m):
	a,b=map(int,input().split())
	connection.add(a)
	connection.add(b)
print(n-len(connection))

Submission status: Wrong Answer

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

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

print(n-(m+1))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
B = []
#j=1
for i in range(M):
    Ai,Bi = map(int,input().split())
    A += [Ai]
    B += [Bi]
#for i in range(N):
    #if(((j in A) == True) or ((j in B) == True)):
#    if(((i+1 in A) == True) or ((i+1 in B) == True)):
#        N -= 1
    #j+=1
TOSI = set(A+B)
#print(TOSI)
num = N - len(TOSI)
print(num)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
B = []
#j=1
for i in range(M):
    Ai,Bi = map(int,input().split())
    A += [Ai]
    B += [Bi]
for i in range(N):
    #if(((j in A) == True) or ((j in B) == True)):
    if(((i+1 in A) == True) or ((i+1 in B) == True)):
        N -= 1
    #j+=1
print(N)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
B = []
for i in range(M):
    Ai,Bi = map(int,input().split())
    A += [Ai]
    B += [Bi]
num = N-(M+1)
print(num)

Submission status: Wrong Answer

Solution code:
import collections
N,M = map(int,input().split())
AB = [list(map(lambda x : int(x)-1,input().split())) for _ in range (M)]
anslist = [i for i in range (N)]
def find(x):
  global anslist
  if anslist[x] == x:
    return x
  else:
    anslist[x] = find(anslist[x])
    return anslist[x]
def unite(x,y):
  global anslist
  if find(x) != find(y):
    anslist[x] = find(y)
    return
for i in range (M):
  unite(AB[i][0],AB[i][1])
for i in range (N):
  find(i)
anscount = collections.Counter(anslist)
ans = len(anscount) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N,M = map(int,input().split())
AB = [list(map(lambda x : int(x)-1,input().split())) for _ in range (M)]
anslist = [i for i in range (N)]
def find(x):
  global anslist
  if anslist[x] == x:
    return x
  else:
    anslist[x] = find(anslist[x])
    return anslist[x]
def unite(x,y):
  global anslist
  if find(x) != find(y):
    anslist[x] = find(y)
    return
for i in range (M):
  unite(AB[i][0],AB[i][1])
anscount = collections.Counter(anslist)
ans = len(anscount) - 1
print(ans)

Submission status: Wrong Answer

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

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

for _ in range(M):
    A, B = map(int, input().split())
    same(A, B)
    
print(len(set(parents)) - 2)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        tank = []
        while par[x] >= 0:
            tank.append(x)
            x = par[x]
        for elt in tank:
            par[elt] = x
        return x
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#集合の数
def numb():
    s = list(set(par))
    l = len(s)
    num = 0
    for ij in range(l):
        if s[ij] < 0:
            num += 1
    return num

n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))
par = [-1]*(n+1)
for j in range(m):
    unite(ab[j][0], ab[j][1])
print(numb() - 1)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
par = [i for i in range(n+1)]

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)
    par[x] = y

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

par.pop(0)
l = set(par)

print(len(l) - 1)

Submission status: Wrong Answer

Solution code:
def union(x,y):
    a[y]=x
    return a

def find(x):
    if a[x] == -1:
        print(5)
        return x
    return find(a[x])

N,M = map(int,input().split())
a=[-1]*N
for i in range(0,M):
    Q,W = map(int,input().split())
    union(Q-1,W-1)

ans=0
while a.count(-1) > 1:
    xx = -1
    for i in range(0, len(a) ):
        if a[i] == -1 and xx > -1:
            union(xx,i)
            ans += 1
            break
        if a[i] == -1 and xx == -1:
            xx=i

print(ans)

Submission status: Wrong Answer

Solution code:
def union(x,y):
    a[y]=x
    return a

def find(x):
    if a[x] == -1:
        print(5)
        return x
    return find(a[x])

N,M = map(int,input().split())
a=[-1]*N
for i in range(0,M):
    Q,W = map(int,input().split())
    union(Q-1,W-1)


print(a)
ans=0
while a.count(-1) > 1:
    xx = -1
    for i in range(0, len(a) ):
        if a[i] == -1 and xx > -1:
            union(xx,i)
            ans += 1
            break
        if a[i] == -1 and xx == -1:
            xx=i

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
for _ in range(m):
    a,b = map(int,input().split())
print(n-m-1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = [list(map(int, input().split())) for i in range(m)]
y = list(map(list, set(map(tuple, x))))
z = len(y)
print(n-1-z)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


def solve():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        a,b = map(int, input().split())
        uf.union(a,b)
    print(uf.group_count() - 1)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
(N,M),*AB=[list(map(int, x.split())) for x in open(0).readlines() if len(x)>1] 
d={}                                                                           
g=0                                                                            
for a,b in AB:                                                                 
    pass

Submission status: Wrong Answer

Solution code:
(N,M),*AB=[list(map(int, x.split())) for x in open(0).readlines()]

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
r = {}
s = set()
g = 0
for i in range(m):
  a, b = map(int, input().split())
  if a not in s and b not in s:
    r[a] = g
    r[b] = g
    g += 1
    s.add(a)
    s.add(b)
  elif a in s:
    r[b] = r[a]
    s.add(b)
  elif b in s:
    r[a] = r[b]
    s.add(a)
ans = g - 1 + n - len(list(s))
print(ans)

Submission status: Wrong Answer

Solution code:
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'




def solve():
    n, m = map(int, input().split())

    adj_list = {x: [] for x in range(1, n + 1)}

    uf = [-1] * (n + 1)

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

    # print(uf)

    sets = 0
    
    for i in range(1, n + 1):
        if uf[i] == i or uf[i] == -1:
            sets += 1

    cout<<sets - 1<<endl




def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'




def solve():
    n, m = map(int, input().split())

    adj_list = {x: [] for x in range(1, n + 1)}

    uf = [-1] * (n + 1)

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

    print(uf)

    sets = 0
    
    for i in range(1, n + 1):
        if uf[i] == i or uf[i] == -1:
            sets += 1

    cout<<sets - 1<<endl




def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'




def solve():
    n, m = map(int, input().split())

    adj_list = {x: [] for x in range(1, n + 1)}

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

    sets = 0
    visited = {}

    def bfs(curr_node):
        nonlocal visited

        q = [curr_node]

        while q:
            ele = q.pop(0)
            visited[ele] = True
            
            for i in adj_list[curr_node]:
                if i not in visited:
                    q.append(i)
    
    for i in range(1, n + 1):
        if i not in visited:
            sets += 1
            bfs(i)

    cout<<sets - 1<<endl




def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

roads=[]

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

group2=[]

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

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

print(counter-1)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

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

    def is_same_group(self, x, y):
        return self.get_root(x) == self.get_root(y)

    def count(self, x):
        return -self.root[self.get_root(x)]

    def unite(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)

        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1


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

ans = 0
for i in range(N):
    ans = max(ans, uf.get_root(i))
print(ans - 1)

Submission status: Wrong Answer

Solution code:
i = list(map(int, input().split()))
p = [map(int, input().split()) for _ in range(i[1])]
print(i[0]-1-i[1])

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, M = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]

    def unite(self, x, y):
        if not self.same(x, y):
            self.root[self.find(y)] = self.find(x)

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
UF = UnionFind(N)
for _ in range(M):
  x, y = map(int, input().split())
  if not UF.same(x-1, y-1):
    UF.unite(x-1, y-1)
UC = Counter(UF.root)
print(len(UC)-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
roots = []
for m in range(M):
  root = list(map(int,input().split()))
  roots.append(root)
  
print(roots)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, M = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]

    def unite(self, x, y):
        if not self.same(x, y):
            self.root[self.find(y)] = self.find(x)

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
UF = UnionFind(N)
for _ in range(M):
  x, y = map(int, input().split())
  UF.unite(x-1, y-1)
UC = Counter(UF.root)
print(len(UC)-1)

Submission status: Wrong Answer

Solution code:
import collections
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range (M)]
anslist = [i for i in range (N)]
def ketugou(x,y):
  global anslist
  if anslist[x-1] != anslist[y-1]:
    anslist = [anslist[x-1] if anslist[i]==anslist[y-1] else anslist[i] for i in range (N)]
for i in range (M):
  ketugou(AB[i][0],AB[i][1])
anscount = collections.Counter(anslist)
ans = len(anscount)
print(ans)

Submission status: Wrong Answer

Solution code:
f = lambda x: x if p[x]<0 else f(p[x])
N,M = map(int,input().split())
p = [-1]*N
for _ in range(M):
  A,B = map(lambda x:f(int(x)-1),input().split())
  if A==B: continue
  elif A<B: A,B=B,A
  p[A] += p[B]
  p[B] = A
  print(p)
print(sum(i<0 for i in p)-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
roads = [list(map(int, input().split())) for _ in range(M)]
print(N-M-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
ans = N-1
d = []
for m in range(M):
  A,B = map(int,input().split())
  for i,di in enumerate(d):
    if set([A,B]).issubset(di):
      d[i] = di|set([A,B])
      break
  else:
    d.append(set([A,B]))
    ans -= 1
print(ans)
print(d)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def find(x):
    if par[x] == -1:
        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:
        return 0
    par[x] = y
    
for i in range(M):
    a,b = map(int,input().split())
    unite(a,b)
print(N-len([i for i in par if i == -1]))

Submission status: Wrong Answer

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

def find(x):
    if par[x] == -1:
        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:
        return 0
    par[x] = y
    
for i in range(M):
    a,b = map(int,input().split())
    unite(a,b)
print(len([i for i in par if i == -1]))