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: Accepted

Solution code:
#unionfind
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 _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.union(a,b)
s=set()
for i in range(n):
    s.add(uf.find(i))
print(len(s)-1)

Submission status: Accepted

Solution code:
def root(x):
    if r[x] < 0:
        return x
    else:
        r[x] = root(r[x])
        return r[x]
def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        if r[x] > r[y]:
            x,y = y,x
        r[x] += r[y]
        r[y] = x
n,m = map(int,input().split())
r = [-1] * n
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a,b)
ans = 0
for i in r:
    if i < 0:
        ans += 1
print(ans-1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict

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):
        self.all_group_member=defaultdict(list)
        for i in range(self.n):
            self.all_group_member[self.find(i)].append(i)
        return self.all_group_member

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots()) 
 
def main():
    n,m=map(int, input().split())
    uf = UnionFind(n+1)
    for _ in range(m):
        a,b=map(int, input().split())
        uf.union(a, b)  # aとbをマージ
    print(uf.group_count()-2)
    #for group in uf.to_sets():  # すべてのグループのリストを返す
        #print(group)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*n
        

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

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

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                #ランクの更新
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1


N,M = map(int,input().split())
ufpc = UnionFindPathCompression(N)
for i in range(M):
    a,b = map(int,input().split())
    ufpc.union(a-1,b-1)

ans = 0
for i in range(N-1):
    if ufpc.find(i) != ufpc.find(i+1):
        ufpc.union(i,i+1)
        ans += 1
print(ans)

Submission status: Accepted

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

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

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

n,m = readints()
u = UnionFind(n)
for i in range(m):
    a,b = readints()
    u.unite(a-1,b-1)

print(sum([1 for x in u.par if x<0])-1)

Submission status: Accepted

Solution code:
class Unionfind():  # 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 group_cnt(self):  # グループの数
        return sum(x < 0 for x in self.parents)

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

uf = Unionfind(n)
for a, b in ab:
    uf.union(a - 1, b - 1)
print(uf.group_cnt() - 1)

Submission status: Accepted

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 _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
print(len(uf.roots())-1)

Submission status: Accepted

Solution code:
def main():
    def find(target):
        if parent[target] < 0:
            return target
        else:
            parent[target] = find(parent[target])
            return parent[target]

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

    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x == root_y:
            return
        if parent[root_x] > parent[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_x] += parent[root_y]
        parent[root_y] = root_x

    # 今回これ使わないけど、どこに誰がいるのかはこれでわかる
    def members(n, x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    def get_size(x):
        return -parent[find(x)]

    def get_root():
        return [i for i, root in enumerate(parent) if root < 0]
    
    n, m = map(int, input().split())
    parent = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        union(a, b)
    ans = len(get_root()) - 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# union-find
class UnionFind:
    def __init__(self, n):
        self.prsz = [-1] * n # parent & size
    def find(self, v): # root
        if self.prsz[v] < 0: return v
        self.prsz[v] = self.find(self.prsz[v])
        return self.prsz[v]
    def union(self, v, u): # unite
        v = self.find(v); u = self.find(u)
        if v == u: return False
        if self.prsz[v] > self.prsz[u]: v, u = u, v # size(v) < size(u)
        self.prsz[v] += self.prsz[u]
        self.prsz[u] = v
        return True

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    uf.union(a, b)
ans = -1
for a in uf.prsz:
    if a < 0: ans += 1
print(ans)

Submission status: Accepted

Solution code:
# union-find
class UnionFind:
    def __init__(self, n):
        self.prsz = [-1] * n # parent & size
    def find(self, v): # root
        if self.prsz[v] < 0: return v
        self.prsz[v] = self.find(self.prsz[v])
        return self.prsz[v]
    def union(self, v, u): # unite
        v = self.find(v); u = self.find(u)
        if v == u: return False
        if self.prsz[v] > self.prsz[u]: v, u = u, v # size(v) < size(u)
        self.prsz[v] += self.prsz[u]
        self.prsz[u] = v
        return True

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

Submission status: Accepted

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

    def find(self, x) -> int:
        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) -> None:
        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) -> int:
        return -self.parents[self.find(x)]

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

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

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

    def group_count(self) -> int:
        return len(self.roots())

    def all_group_members(self) -> dict:
        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=UnionFind(n)
for i in range(m):
    b,c=map(int,input().split())
    a.union(b-1,c-1)
print(a.group_count()-1)

Submission status: Accepted

Solution code:
# union-find
class UnionFind:
    def __init__(self, n):
        self.prsz = [-1] * n # parent & size
    def find(self, v): # root
        if self.prsz[v] < 0: return v
        self.prsz[v] = self.find(self.prsz[v])
        return self.prsz[v]
    def union(self, v, u): # unite
        v = self.find(v); u = self.find(u)
        if v == u: return False
        if self.prsz[v] > self.prsz[u]: v, u = u, v # size(v) < size(u)
        self.prsz[v] += self.prsz[u]
        self.prsz[u] = v
        return True

n, m = map(int, input().split())
uf = UnionFind(n)
ans = n - 1
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    if uf.find(a) !=uf.find(b):
        uf.union(a, b)
        ans -= 1
print(ans)

Submission status: Accepted

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

    def find(self, x) -> int:
        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) -> None:
        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) -> int:
        return -self.parents[self.find(x)]

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

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

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

    def group_count(self) -> int:
        return len(self.roots())

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

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

def main():
    N: int
    M: int
    A: int
    B: int
    N, M = map(int, input().split())
    uni = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        uni.union(A,B)
    
    print(uni.group_count() - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
print(uf.group_count() - 1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ？
        return self.find(x)==self.find(y)
    def members(self,x):
        #xと同じグループに属する要素のリスト
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        #全ての根の要素のリスト
        return [i for i, x in enumerate(self.parents) if x<0]
    def group_count(self):
        #グループの数
        return len(self.roots())
    def all_group_members(self):
        #各ルート要素のグループに含まれる要素のリストの辞書
        return {r: self.members(r) for r in self.roots()}
    def all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

def main():
    n, m = map(int,input().split())
    AB_union = UnionFind(n)
    for i in range(m):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        AB_union.unite(a, b)
    print(AB_union.group_count() - 1)



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:

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

def g(u,parent):
    if parent[u]!= u:
        parent[u] = g(parent[u], parent)
    return parent[u]
parent = range(n+1)
for _ in range(m):
    u,v = map(int, raw_input().split())
    pu,pv = g(u,parent), g(v,parent)
    if pu!= pv:
        parent[pu] = pv

ans = 0
for u in range(1, n+1):
    if g(u,parent) == u:
        ans+=1
print ans -1

Submission status: Accepted

Solution code:

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

def g(u,parent):
    if parent[u]!= u:
        parent[u] = g(parent[u], parent)
    return parent[u]
parent = {u:u for u in range(1, n+1)}
for _ in range(m):
    u,v = map(int, raw_input().split())
    pu,pv = g(u,parent), g(v,parent)
    if pu!= pv:
        parent[pu] = pv

ans = 0
for u in parent:
    if g(u,parent) == u:
        ans+=1
print ans -1

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

from collections import defaultdict

n,m=map(int,input().split())
visited=[0]*n
d=defaultdict(list)
def dfs(n):
    visited[n]=1
    #print(visited)
    for i in d[n]:
        if visited[i]==0:
            dfs(i)

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

r=-1
for i in range (n):
    if visited[i]==0:
        dfs(i)
        r+=1
print(r)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    # マイナスの場合は leader であり、同時にサイズ(*-1)を保持する
    uf = [-1] * (n+1)

    def uf_leader(a):
        if uf[a]<0:
            return a
        uf[a] = uf_leader(uf[a])
        return uf[a]
    def uf_unite(a, b):
        ua, ub = uf_leader(a), uf_leader(b)
        if ua==ub:
            return False
        if uf[ua] > uf[ub]:
            ua, ub = ub, ua
        uf[ua] += uf[ub]
        uf[ub] = ua
        return True
    def uf_leaders():
        return [v for v in range(1,n+1) if uf[v]<0]

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

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

main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    # マイナスの場合は leader であり、同時にサイズ(*-1)を保持する
    uf = [-1] * (n+1)

    def uf_leader(a):
        if uf[a]<0:
            return a
        uf[a] = uf_leader(uf[a])
        return uf[a]
    def uf_unite(a, b):
        ua, ub = uf_leader(a), uf_leader(b)
        if ua==ub:
            return False
        if uf[ua] > uf[ub]:
            ua, ub = ub, ua
        uf[ua] += uf[ub]
        uf[ub] = ua
        return True
    def uf_leaders():
        return set([uf_leader(v) for v in range(1,n+1)])

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

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

main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    # マイナスの場合は leader であり、同時にサイズ(*-1)を保持する
    uf = [-1] * (n+1)

    def uf_leader(a):
        if uf[a]<0:
            return a
        uf[a] = uf_leader(uf[a])
        return uf[a]
    def uf_unite(a, b):
        ua, ub = uf_leader(a), uf_leader(b)
        if ua==ub:
            return False
        if uf[ua] > uf[ub]:
            a, b = b, a
        uf[ua] += uf[ub]
        uf[ub] = ua
        return True
    def uf_leaders():
        return set([uf_leader(v) for v in range(1,n+1)])

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

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

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
road = [[] for _ in range(N+1)]
visit = [0]*(N+1)

for i in range(M):
    x,y = map(int,readline().split())
    road[x].append(y)
    road[y].append(x)
  
def dfs(v,prev):
    for x in road[v]:
        if x == prev:
            continue
        if visit[x] != 0:
            continue
        visit[x] = 1
        dfs(x,v)
    return 

count = 0     
for i in range(1,N+1):
    if visit[i] == 0:
        dfs(i,-1)
        count += 1

print(count-1)

Submission status: Accepted

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 a
        elif uf[a]==a:
            return a
        uf[a] = uf_find(uf[a])
        return uf[a]
    def uf_union(a, b):
        if uf_find(a)==uf_find(b):
            return
        ua, ub = uf_find(a), uf_find(b)
        if ua>ub:
            ua, ub = ub, ua
        uf[ub] = ua
    def uf_leaders():
        return set([uf_find(v) for v in range(1,n+1)])

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

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

main()

Submission status: Accepted

Solution code:
#Code by Sounak, IIESTS
#------------------------------warmup----------------------------

import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading



sys.setrecursionlimit(300000)
threading.stack_size(10**8)


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)
input = lambda: sys.stdin.readline().rstrip("\r\n")

#-------------------game starts now-----------------------------------------------------
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]
 
    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]
 
    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]
 
    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]
 
 
class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)
 
    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
#-------------------------------------------------------------------------

def main():
    n,m=map(int,input().split())
    visited=[0]*n
    d=defaultdict(list)
    def dfs(n):
        visited[n]=1
        #print(visited)
        for i in d[n]:
            if visited[i]==0:
                dfs(i)
    
    for i in range (m):
        a,b=map(int,input().split())
        a,b=a-1,b-1
        d[a].append(b)
        d[b].append(a)
    
    r=-1
    for i in range (n):
        if visited[i]==0:
            dfs(i)
            r+=1
    print(r)
    
t = threading.Thread(target=main)
t.start()
t.join()

Submission status: Accepted

Solution code:
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
 a,b=sorted(map(r:=lambda x:x*(p[x]<0)or r(p[x]),a),key=p.__getitem__)
 if a-b:p[a]+=p[b];p[b]=a
print(sum(i<0for i in p)-2)

Submission status: Accepted

Solution code:
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
 a,b=map(r:=lambda x:x*(p[x]<0)or r(p[x]),a)
 if a-b:
  if p[a]>p[b]:a,b=b,a
  p[a]+=p[b];p[b]=a
print(sum(i<0for i in p)-2)

Submission status: Accepted

Solution code:
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
 a,b=map(r:=lambda x:x*(p[x]<0)or r(p[x]),a)
 if a!=b:
  if p[a]>p[b]:a,b=b,a
  p[a]+=p[b];p[b]=a
print(sum(i<0for i in p)-2)

Submission status: Accepted

Solution code:
r=lambda x:x*(p[x]<0)or r(p[x])
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
    a,b=map(r,a)
    if a==b:continue
    if p[a]>p[b]:a,b=b,a
    p[a]+=p[b]
    p[b]=a
print(sum(i<0for i in p)-2)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

checked = [False]*n
q = deque([])
cnt = 0

#連結成分のカウント

for i in range(n):
    if checked[i]:
        continue
    checked[i] = True
    q.append(i)
    while q:
        v = q.pop()
        s = g[v]
        for j in s:
            if checked[j]:
                continue
            checked[j] = True
            q.append(j)
    cnt += 1

print(cnt - 1)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

dist = [-1]*n
q = deque([])
cnt = 0

#連結成分のカウント

for i in range(n):
    if dist[i] != -1:
        continue
    dist[i] = 0
    q.append(i)
    while q:
        v = q.pop()
        s = g[v]
        for j in s:
            if dist[j] != -1:
                continue
            dist[j] = 0
            q.append(j)
    cnt += 1

print(cnt - 1)