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:
def main():
    n, m = map(int, input().split())
    uf = [-1] * (n+1)

    def uf_find(a):
        if uf[a]<0:
            uf[a] = a
        return uf[a]
    def uf_union(a, b):
        if uf_find(a)==uf_find(b):
            return
        if b>a:
            a, b = b, a
        uf[b] = uf_find(a)
    def uf_leaders():
        return [v for v in range(1,n+1) if uf[v]==v or uf[v]==-1]

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

    # print(uf)
    
    ans = len(uf_leaders())-1
    print(ans)

main()

Submission status: Wrong Answer

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

ans = 0

class UnionFind:
    def __init__(self,n):
        self.root = [i for i in range(n+1)]

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

    def Unite(self,x,y):
        x = self.Root_Find(x)
        y = self.Root_Find(y)
        if x == y:
            return
        self.root[y] = x

tree = UnionFind(n)

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

for i in range(n+1):
    tree.Root_Find(i)
    
print(list(set(tree.root)))
ans = len(list(set(tree.root))) - 2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
d=defaultdict(int)

for i in range(m):
	a,b=map(int,input().split())
	d[a]+=1
	d[b]+=1
	
count=0
count_1=0
for i in range(1,n+1):
	if d[i]==0:
		count+=1
	elif d[i]==1:
		count_1+=1
		
	
if count_1>0:
	print(count+1)
else:
	print(count)

Submission status: Wrong Answer

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

ans = 0

class UnionFind:
    def __init__(self,n):
        self.root = [i for i in range(n+1)]

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

    def Unite(self,x,y):
        x = self.Root_Find(x)
        y = self.Root_Find(y)
        if x == y:
            return
        self.root[y] = x

tree = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    tree.Unite(a,b)
    
ans = len(list(set(tree.root))) - 2
print(ans)

Submission status: Wrong Answer

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

ans = 0

class UnionFind:
    def __init__(self,n):
        self.root = [i for i in range(n+1)]

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

    def Unite(self,x,y):
        x = self.Root_Find(x)
        y = self.Root_Find(y)
        if x == y:
            return
        self.root[y] = x

tree = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    tree.Unite(a,b)
    
ans = len(list(set(tree.root))) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
"""
Union-Find Tree / Disjoint Set Union (DSU)
"""


def init_unionfind(N):
    global parent, rank, NUM_VERTEX
    NUM_VERTEX = N
    parent = [-1] * N
    rank = [0] * N


def find_root(x):
    p = parent[x]
    if p == -1:
        return x
    p2 = find_root(p)
    parent[x] = p2
    return p2


def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if x == y:
        return  # already united
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def is_connected(x, y):
    return (find_root(x) == find_root(y))


def num_components():
    return len(set(find_root(x) for x in range(NUM_VERTEX)))

# --- end of library ---


def main_yosupo():
    # verified: https://judge.yosupo.jp/problem/unionfind
    N, Q = [int(x) for x in input().split()]
    init_unionfind(N)
    for q in range(Q):
        typ, u, v = [int(x) for x in input().split()]
        if typ == 0:
            unite(u, v)
        else:
            print(1 if is_connected(u, v) else 0)


def main_abl():
    N, M = map(int, input().split())
    init_unionfind(N)
    for _i in range(M):
        a, b = map(int, input().split())
        unite(a - 1, b - 1)

    return num_components() - 1


if __name__ == "__main__":
    # main_yosupo()
    main_abl()

Submission status: Wrong Answer

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

ans = 0
edge = [[] for i in range(n)]
flag = [0] * n
v = []
count = 0
for i in range(m):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

for i in range(n):
    if flag[i] == 0:
        ans += 1
        while len(edge[i]) > 0:
            v = edge[i].pop()
            flag[v-1] = 1
            if len(edge[v-1]) > 0:
                v = edge[v-1].pop()
                edge[i].append(v)

print(ans-1)

Submission status: Wrong Answer

Solution code:

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
                self.size[x] += self.size[y]
                self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def siz(self, x):
        x = self.find(x)
        return self.size[x]


N, M = map(int, input().split())
UF = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    UF.union(a, b)
Ans = set(UF.par)
print(len(Ans) - 1)

Submission status: Wrong Answer

Solution code:
#最も上にいる親をたどる
def root(x):
  if r[x] < 0:
    return x
  else:
    #r[x] = root(r[x])
    return root(r[x])

#from operator import itemgetter

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

#print(g)

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

group_num = 1;

for i, x in enumerate(road):
  city_a = x[0]
  city_b = x[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  #print("x1", x1, "x2", x2)
  
  if r[city_a_par] == -1 and r[city_b_par] == -1:
    r[city_b] = city_a_par
  elif r[city_a_par] == -1 or r[city_b_par] == -1:
    if r[city_a_par] > r[city_b_par]:
      r[city_b] = r[city_a_par]
    else:
      r[city_a] = r[city_b_par]
  else:
    if r[city_a_par] > r[city_b_par]:
      r[city_a] = r[city_b_par]
    else:
      r[city_b] = r[city_a_par]
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
class CConnectCities():
    
    def main(self):
        N, M = map(int, input().split())
        road = np.array([list(map(int, input().split())) for l in range(M)]) - 1
        fill = np.zeros(N)
        fill[road] = 1
        print(int(N - np.sum(fill)))
        

if __name__ == "__main__":
    this_class = CConnectCities()
    this_class.main()

Submission status: Wrong Answer

Solution code:
#最も上にいる親をたどる
def root(x):
  if r[x] < 0:
    return x
  else:
    r[x] = root(r[x])
    return r[x]

#from operator import itemgetter

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

#print(g)

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

group_num = 1;

for i, x in enumerate(road):
  city_a = x[0]
  city_b = x[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  #print("x1", x1, "x2", x2)
  
  if r[city_a_par] == -1 and r[city_b_par] == -1:
    r[city_b] = city_a_par
  elif r[city_a_par] == -1 or r[city_b_par] == -1:
    if r[city_a_par] > r[city_b_par]:
      r[city_b] = r[city_a_par]
    else:
      r[city_a] = r[city_b_par]
  else:
    if r[city_a_par] > r[city_b_par]:
      r[city_a] = r[city_b_par]
    else:
      r[city_b] = r[city_a_par]
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
not_connected = [1]*n
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    not_connected[a]=0
    not_connected[b]=0
print(sum(not_connected))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [[] for i in range(n)]
ll = []
vis = [0]*n
ans = 0

for i in range(m):
    x, y = map(int, input().split())
    a = min(x, y) - 1
    b = max(x, y) - 1
    l[a].append(b)


for i in range(n):
    cnt = len(l[i])
    if len(l[i]) == 0: #追加の連結なしなら
        if vis[i] == 0:
            vis[i] = 1
            ans += 1
    else: #追加の連結がある場合
        if vis[i] == 0: #初訪問なら
            vis[i] = 1 #訪問済みにする
            ans += 1
        for j in l[i]: #連結対象を読み出す
            vis[j] = 1 #訪問済みにする

print(ans - 1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [[] for i in range(n)]
ll = []
vis = [0]*n
ans = 0

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

ll = sorted(ll)

for i, j in ll:
    l[i].append(j)

for i in range(n):
    cnt = len(l[i])
    if len(l[i]) == 0: #追加の連結なしなら
        if vis[i] == 0:
            vis[i] = 1
            ans += 1
    else: #追加の連結がある場合
        if vis[i] == 0: #初訪問なら
            vis[i] = 1 #訪問済みにする
            ans += 1
        for j in l[i]: #連結対象を読み出す
            vis[j] = 1 #訪問済みにする

print(ans - 1)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    __slots__ = ["N", "root"]

    def __init__(self, N):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        """
        self.N = N
        self.root = [-1] * N

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

    def find(self, x):
        """頂点xの根を見つける"""
        r = x
        while self.root[r] >= 0:
            r = self.root[r]

        while self.root[x] >= 0:
            self.root[x], x = r, self.root[x]

        return r

    def union(self, x, y):
        """x, yが属する木をunion"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.root[y] < self.root[x]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

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

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    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.root) 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()}


import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    x, y = map(int, input().split())
    uf.union(x - 1, y - 1)
k = uf.group_count()
print(n - k)

Submission status: Wrong Answer

Solution code:
class DisjointSets:
    def __init__(self, n):
        self.nodes = [-1] * n #根にサイズを負の値で格納する。
    def find(self, i):
        if self.nodes[i] < 0: #値が負の場合は根
            return i
        else:
            self.nodes[i] = self.find(self.nodes[i]) #縮約
            return self.nodes[i]
    def unite(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i == j:
            return
        if self.nodes[i] > self.nodes[j]: #サイズ比較してiの方がサイズが大きいようにする
            i, j = j, i
        self.nodes[i] += self.nodes[j] #大きい方に小さい方を統合しサイズを登録する。
        self.nodes[j] = i # jの親はi
    
    def size(self, i): # 所属する集合の大きさを返す
        i = self.find(i)
        return -self.nodes[i]

n, m = map(int, input().split())
ds = DisjointSets(n)
for _ in range(m):
    a, b = map(lambda x:int(x)-1, input().split())
    ds.unite(a, b)

print(len(set(ds.find(i) for i in ds.nodes)) - 1)

Submission status: Wrong Answer

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])
uf = [i for i in range(N)]
for i in range(M):
  l = input().split()
  la = int(l[0])
  lb = int(l[1])
  minN = min(uf[la-1],uf[lb-1],la-1,lb-1)
  a = uf[la-1]
  b = uf[lb-1]
  for j in range(N):
    if(a==uf[j]) or (b==uf[j]):
      uf[j] = minN
  #uf[la-1] = minN
  #uf[lb-1] = minN


print(uf)
s = set(uf)
print(s)
print(len(s)-1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [[] for i in range(n)]
vis = [0]*n
ans = 0

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

for i in range(n):
    cnt = len(l[i])
    if len(l[i]) == 0: #追加の連結なしなら
        if vis[i] == 1: #訪問済みなら次に行く
            continue
        else: #初訪問なら
            vis[i] = 1 #訪問済みにする。
            ans += 1 #1増やす
    else: #連結がある場合
        if vis[i] == 0: #初訪問なら
            vis[i] = 1 #訪問済みにする
            ans += 1 #1増やす
        for j in l[i]: #連結対象を読み出す
            vis[j] = 1 #訪問済みにする

print(ans - 1)

Submission status: Wrong Answer

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])
arr = [0]*N
retval = 0
uf = [i for i in range(N)]
for i in range(M):
  l = input().split()
  #A[i] = l[0]
  #B[i] = l[1]
  minN = min(uf[int(l[0])-1],uf[int(l[1])-1],int(l[0]),int(l[1]))
  uf[int(l[0])-1] = minN
  uf[int(l[1])-1] = minN

#print(uf)
s = set(uf)
#print(s)
print(len(s)-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#　n個分の入力
N, M = map(int, input().split())

l = []
flag = 0
for loop in range(M):
    x, y = map(int, input().split())
    if len(l) > 0:
        flag = 0
        for i in range(len(l)):
            if (x in l[i]):
                flag = 1
                if (y in l[i]):
                    pass
                else:
                    flag2 = 0
                    for j in range(i, len(l)):
                        if y in l[j]:
                            for k in range(len(l[j])):
                                l[i].append(l[j][k])
                            l.remove(l[j])
                            flag2 =1
                            break
                    if flag2 ==0:
                        l[i].append(y)
            if flag == 1:
                break
        if flag ==0:
            l.append([x,y])
    else:
        l.append([x,y])
    #print(l)

count = 0
for i in range(len(l)):
    count = count + len(l[i])
print(N-count+len(l)-1)

Submission status: Wrong Answer

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])
arr = [0]*N
retval = 0
uf = [i for i in range(N)]
for i in range(M):
  l = input().split()
  #A[i] = l[0]
  #B[i] = l[1]
  minN = min(uf[int(l[0])-1],uf[int(l[1])-1],int(l[0]),int(l[1]))
  uf[int(l[0])-1] = minN
  uf[int(l[1])-1] = minN

#print(uf)
print(max(uf)-1)

Submission status: Wrong Answer

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])
arr = [0]*N
retval = 0
uf = [i for i in range(N)]
for i in range(M):
  l = input().split()
  #A[i] = l[0]
  #B[i] = l[1]
  minN = min(uf[int(l[0])-1],uf[int(l[1])-1],int(l[0]),int(l[1]))
  uf[int(l[0])-1] = minN
  uf[int(l[1])-1] = minN

print(uf)
print(max(uf)-1)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind:
    from typing import List, Set

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n

    def merge(self, x, y) -> int:
        x = self.leader(x)
        y = self.leader(y)

        if x == y:
            return 0

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

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

        return self.parent[x]

    def same(self, x, y) -> bool:
        return self.leader(x) == self.leader(y)

    def leader(self, x) -> int:
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.leader(self.parent[x])
            return self.parent[x]

    def size(self, x) -> int:
        return -self.parent[self.leader(x)]

    def groups(self) -> List[Set[int]]:
        groups = dict()

        for i in range(self.n):
            p = self.parent[i]
            if p < 0:
                p = i
            if not groups.get(p):
                groups[p] = set()
            groups[p].add(i)

        return list(groups.values())


def main():
    N, M = map(int, input().split())

    uf = UnionFind(N)

    for _ in range(M):
        A, B = map(lambda x: int(x) - 1, readline().split())
        uf.merge(A, B)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind:
    from typing import List, Set

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n

    def merge(self, x, y) -> int:
        x = self.leader(x)
        y = self.leader(y)

        if x == y:
            return -1

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

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

        return self.parent[x]

    def same(self, x, y) -> bool:
        return self.leader(x) == self.leader(y)

    def leader(self, x) -> int:
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.leader(self.parent[x])
            return self.parent[x]

    def size(self, x) -> int:
        return -self.parent[self.leader(x)]

    def groups(self) -> List[Set[int]]:
        groups = dict()

        for i in range(self.n):
            p = self.parent[i]
            if p < 0:
                p = i
            if not groups.get(p):
                groups[p] = set()

            groups[p].add(i)

        return list(groups.values())


def main():
    N, M = map(int, input().split())

    uf = UnionFind(N)

    for _ in range(M):
        A, B = map(lambda x: int(x) - 1, readline().split())
        uf.merge(A, B)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

def unite(x, y):
    x = root(x)
    y = root(y)

    if x==y :
        return
    if x < y:
        par[y] = x
    else:
        par[x] = y
        
for i in range(M):
    A, B = list(map(int, input().split()))
    A -= 1
    B -= 1
    unite(A, B)
    
print(len(set(par))-1)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind:
    from typing import List, Set

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n

    def merge(self, x, y) -> None:
        x = self.leader(x)
        y = self.leader(y)

        if x == y:
            return
        if self.parent[x] < self.parent[y]:
            x, y = y, x

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

    def same(self, x, y) -> bool:
        return self.leader(x) == self.leader(y)

    def leader(self, x) -> int:
        if self.parent[x] < 0:
            return x
        else:
            return self.leader(self.parent[x])

    def size(self, x) -> int:
        return -self.parent[self.leader(x)]

    def groups(self) -> List[Set[int]]:
        groups = dict()

        for i in range(self.n):
            p = self.parent[i]
            if p < 0:
                p = i
            if not groups.get(p):
                groups[p] = set()

            groups[p].add(i)

        return list(groups.values())


def main():
    N, M = map(int, input().split())

    uf = UnionFind(N)

    for _ in range(M):
        A, B = map(lambda x: int(x) - 1, readline().split())
        uf.merge(A, B)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [[] for i in range(n)]
vis = [0]*n
ans = 0

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

for i in range(n):
    if len(l[i]) == 0:
        if vis[i] == 1:
            continue
        else:
            vis[i] = 1
            ans += 1
    else: #つながりがある場合
        if vis[i] == 0: #事前につながっていない場合
            vis[i] = 1
            ans += 1
        for j in l[i]:
            vis[j] = 1

print(ans - 1)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split(' '))
T = [0]*n

print(n-m-1)

Submission status: Wrong Answer

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])
arr = [0]*N
retval = 0
for i in range(M):
  l = input().split()
  #A[i] = l[0]
  #B[i] = l[1]
  arr[int(l[0])-1] = 1
  arr[int(l[1])-1] = 1

for i in range(N):
  retval += arr[i]

print(N-retval)

Submission status: Wrong Answer

Solution code:

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
        d.append(i)
        while d:
            x = d.pop()
            for i in w[x]:
                if c[i] == 0:
                    c[i] = 1
                    d.append(c[i])

print(ans)

Submission status: Wrong Answer

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

parent = [-1] * N


def get_group_root(x):
    if parent[x] < 0:
        return x
    return get_group_root(parent[x])


for i in range(0, M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1

    groupA = get_group_root(A)
    groupB = get_group_root(B)

    if groupA == groupB:
        continue
    elif parent[groupA] < parent[groupB]:
        parent[B] = A
        parent[groupA] -= 1
    else:
        parent[A] = B
        parent[groupB] -= 1


def check(x):
    return x < 0


print(sum(list(map(check, parent))) - 1)

Submission status: Wrong Answer

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

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

    def find(self, x):#親となる要素を探索
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#再帰
            return self.root[x]

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

        elif self.rank[x] > self.rank[y]:#深い木に連結
            self.root[x] += self.root[y]
            self.root[y] = x#yの親をxとする

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def issame(self, x, y):#x, yが同じ集合か判定
            return self.find(x) == self.find(y)


    def count(self, x):#要素の個数
        return (-1)*self.root[self.find(x)]

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

for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)
x=set()
for i in range(n):
    x.add(uf.find(i))
l=len(x)
print(l-1)

Submission status: Wrong Answer

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

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

    def find(self, x):#親となる要素を探索
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#再帰
            return self.root[x]

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

        elif self.rank[x] > self.rank[y]:#深い木に連結
            self.root[x] += self.root[y]
            self.root[y] = x#yの親をxとする

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def issame(self, x, y):#x, yが同じ集合か判定
            return self.find(x) == self.find(y)


    def count(self, x):#要素の個数
        return (-1)*self.root[self.find(x)]

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

for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)
x=[]
for i in range(n):
    x.append(uf.find(i))
l=len(set(x))
print(l-1)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
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(len(set(uf.par[1:]))-1)

Submission status: Wrong Answer

Solution code:
import sys

n,m = map(int, input().split())
ls = []
for i in range(m):
    ls.append(list(map(int, input().split())))

cheker = range(1,n+1)
# for ele in cheker:
#     print(ele)


#phase1 塊を作成
ls2 = []

if m == 1:
    print(n-1-1)
    sys.exit()

for i in range(m-1):
    # print(ls[i])
    ele1 = ls[i]
    for j in range(i+1,len(ls)):
        # print(ls[j])
        if (ele1[0] or ele[1]) in ls[j]:
            ele1 = set(ele1+ls[j])
            ele1 = list(ele1)
            # print(ele1)
            ls2.append(ele1)
            break
# print("ls2",ls2)

ele2 = ls[len(ls)-1]
for ele3 in ls2:
    if (ele2[0] or ele2[1]) in ele3:
        continue
    else:
        ele2 = set(ele2)
        ele2 = list(ele2)
        ls2.append(ele2)
        break
# print("ls2",ls2)

# phase2 足りない街を追加
mn = 0
for ele in ls2:
    mn += len(ele)
# print(mn)

if mn != n:
    print(len(ls2)+(n-mn)-1)
else:
    print(len(ls2)-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
cityList = set()
loadList = []
j = 1
ans = 0
for i in range(M):
    loadList.append(set(list(map(int,input().split()))))
for i in range(N):
    cityList.add(i + 1)
k = 0
while(k != len(loadList)):
    l = k + 1
    j = l
    while(j < len(loadList)):
        if(len(loadList[k] & loadList[j]) != 0):
            loadList[k] = loadList[k] | loadList[j]
            del loadList[j]
            j = l
        else:
            j += 1
    k += 1
gap = cityList - loadList[0]
ans += len(gap)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
d={i+1:[] for i in range(n)}
for i in range(m):
    x,y=map(int,input().split())
    d[x].append(y)
    d[y].append(x)

stack=[1]
visit=set()
ans= 0 
while stack:
    c=stack.pop()
    visit.add(c)
    ans+=1
    for i in d[c]:
        if i not in visit:
            stack.append(i)
print(ans-1)

Submission status: Wrong Answer

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()))
  
class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, 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
        
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

print(ans-1)

Submission status: Wrong Answer

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

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

    def find(self, x):#親となる要素を探索
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#再帰
            return self.root[x]

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

        elif self.rank[x] > self.rank[y]:#深い木に連結
            self.root[x] += self.root[y]
            self.root[y] = x#yの親をxとする

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def issame(self, x, y):#x, yが同じ集合か判定
            return self.find(x) == self.find(y)


    def count(self, x):#要素の個数
        return (-1)*self.root[self.find(x)]

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

for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)
x=[]
for i in range(n):
    if uf.find(i):
        x.append(i)
l=len(x)
print(l-1)