Problem:


Score : 500 points

Problem Statement

There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.

Let A_i be the integer written on the i-th card.

Your objective is to guess A_1, A_2, ..., A_N correctly.

You know the following facts:

For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.

You are a magician and can use the following magic any number of times:

Magic: Choose one card and know the integer A_i written on it. The cost of using this magic is 1.

What is the minimum cost required to determine all of A_1, A_2, ..., A_N?

It is guaranteed that there is no contradiction in given input.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq X_i < Y_i \leq N

1 \leq Z_i \leq 100

The pairs (X_i, Y_i) are distinct.

There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)

Input

Input is given from Standard Input in the following format:

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M

Output

Print the minimum total cost required to determine all of A_1, A_2, ..., A_N.

Sample Input 1

3 1
1 2 1

Sample Output 1

2

You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.

Sample Input 2

6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5

Sample Output 2

2

Sample Input 3

100000 1
1 100000 100

Sample Output 3

99999



Sample input:
3 1
1 2 1


Sample output:
2

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



N, M = MAP()
L = [LIST() for i in range(M)]

tree = UnionFind(N)
for x, y, z in L:
    tree.union(x-1, y-1)

print(tree.group_count())

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
parent=list(range(n))
rank=[0]*n
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]>rank[ry]:
		parent[ry]=rx
	else:
		parent[rx]=ry
		if rank[rx]==rank[ry]:
			rank[ry]+=1

for i in range(m):
	x,y,z=map(int,input().split())
	unite(x-1,y-1)
ans=set()
for i in range(n):
	ans.add(root(i))
print(len(ans))

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())
      
      
def main():
  n,m = map(int,input().split())
  u = UnionFind(n)
  
  for _ in range(m):
    x,y,_ = map(int,input().split())
    u.union(x-1,y-1)
  print(u.group_count())
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [ -1 for _ in range(n) ]
        self._size = n
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def size(self, x):
        return -self.parent[self.find(x)]

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

for i in range(m):
    x, y, z = map(int, input().split())
    x -= 1; y -= 1;
    tree.unite(x, y)

print(tree._size)

Submission status: Accepted

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

def find(x):
    if parents[x] < 0: # 負なら根
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
    
#xとyの属する集合の併合
def unite(x,y):
    x = find(x) # x,yは根の番号にする。
    y = find(y)
    
    if x == y:
        return False
    else:
        if parents[x] > parents[y]: # sizeの大きいほうがx
            x,y = y,x
        parents[x] += parents[y]
        parents[y] = x
        return True

parents=[-1]*n

for i in range(m):
    x,y,z=map(int,input().split())
    unite(x-1,y-1)

ans=0
for i in range(n):
    if parents[i]<0:
        ans+=1
print(ans)

Submission status: Accepted

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


class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, M = map(int, input().split())
uf = UnionFind(N+1)
for _ in range(M):
    X, Y, Z = map(int, input().split())
    uf.unite(X, Y)
root = set()
for i in range(1, N+1):
    root.add(uf.find(i))
print(len(root))

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(1000000000)
    n,m=map(int,input().split())
    G=[[] for _ in range(n)]
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1
        y-=1
        G[x].append(y)
        G[y].append(x)
    
    visited=[True]*n
    def dfs(i):
        visited[i]=False
        for e in G[i]:
            if visited[e]:
                dfs(e)
    
    cnt=0
    for i in range(n):
        if visited[i]:
            cnt+=1
            dfs(i)
    
    print(cnt)  

if __name__=='__main__':
    main()

Submission status: Accepted

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

#Union-Find
par=[i for i in range(n)]
size=[1 for _ in range(n)]
rank=[0 for _ in range(n)]
 
def find(x):#木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
    
def unite(x,y):#併合
    x=find(x)
    y=find(y)
    if x==y:
        return
    if rank[x]>rank[y]:
        par[y]=x
        size[x]+=size[y]
    else:
        par[x]=y
        size[y]+=size[x]
        if rank[x]==rank[y]:
            rank[y]+=1
            
def same(x,y):
    return find(x)==find(y)

for _ in range(m):
    x,y,z=map(int,input().split())
    unite(x-1,y-1)
    
print(len(set([find(i) for i in range(n)])))

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines

# 0-indexed
class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return x
  
  def same(self,x,y):
    return self.root(x)==self.root(y)
  
  def unite(self,x,y):
    x=self.root(x)
    y=self.root(y)
    if x==y:
      return
    if self.size[x]>self.size[y]:
      # 大きい方にくっつける
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(self.root(i))
    return r
  
  def show_parent(self):
    print(self.parent)
    
  def show_size(self):
    print(self.size)
    
N,M=map(int,readline().split())
UF=UnionFind(N)
for i in range(M):
  x,y,z=map(int,readline().split())
  UF.unite(x-1,y-1)
  
print(len(UF.get_roots()))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
XYZ = [LIST() for _ in range(M)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(N)

for X, Y, Z in XYZ:
	uf.union(X-1, Y-1)

print(uf.group_count())

Submission status: Accepted

Solution code:

class UnionFind():
    #要素数nで初期化
    #インスタンス変数の初期化
    def __init__(self, n):
        #root : 木の要素数
        #rnk : 木の高さ(rank)
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    
    """ノードxのrootノードを見つける"""
    def Find_Root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x]) 
            return self.root[x]
    
    """木の合併"""
    def Union(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_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
            
            #rnkが同じ場合
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y] += 1
    
    """xとyが同じグループに所属するか"""
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ノードxが属する木のサイズ"""
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
n,m = map(int,input().split())
uf = UnionFind(n)
for i in range(m):
    x,y,z = map(int,input().split())
    uf.Union(x-1, y-1)
tank = set([])
for i in range(n):
    tank.add(uf.Find_Root(i))
print(len(tank))

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())
A=UnionFind(n)
for i in range(m):
  x,y,z=map(int,input().split())
  A.union(x-1,y-1)
print(A.group_count())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())
 
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[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)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

###具体例###
for _ in range(m):
    x, y, z = [int(x) for x in input().split()]
    unite(x - 1, y - 1)

A = set()

for i in range(n):
    A.add(find(i))

print(len(A))

Submission status: Accepted

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

N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    edges[x].append(y)
    edges[y].append(x)

visited = [False] * N

def dfs(u):
    if visited[u]:
        return

    visited[u] = True
    for v in edges[u]:
        if visited[v]:
            continue
        dfs(v)

ans = 0
for u in range(N):
    if visited[u]:
        continue
    ans += 1
    dfs(u)
print(ans)

Submission status: Accepted

Solution code:
N, M = (int(i) for i in input().split())
uf = [-1]*N
def parent(v):
    if uf[v] < 0:
        return v
    else:
        uf[v] = parent(uf[v])
        return uf[v]

def size(v):
    return -uf[parent(v)]

def union(u, v):
    pu = parent(u)
    pv = parent(v)
    if pu != pv:
        res = uf[pv] * uf[pu] #適当な返り値
        uf[pv] += uf[pu]
        uf[pu] = pv
    else:
        res = 0
    return res

for i in range(M):
    X, Y, Z = (int(i) for i in input().split())
    union(X-1, Y-1)
ans = 0
for i in range(N):
    if uf[i] < 0:
        ans += 1
print(ans)

Submission status: Accepted

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


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

    # xの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # xとyを統合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

    # xのメンバーの要素を返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

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

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

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


N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for _ in range(M)]

uf = UnionFind(N)

for x, y, z in XYZ:
    uf.union(x-1, y-1)

ans = uf.group_count()

print(ans)

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(list(self.roots()))

N,M=map(int, input().split())
XYZ=[tuple(map(int, input().split())) for _ in range(M)]
UF=UnionFind(N)
for x,y,_ in XYZ:
    UF.union(x-1,y-1)
print(UF.group_count())

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

N,M=map(int,input().split())
X=[0 for i in range(M)]
Y=[0 for i in range(M)]
Z=[0 for i in range(M)]
for i in range(0,M):
    X[i],Y[i],Z[i]=map(int,input().split())

u=UnionFindVerSize(N)
for i in range(0,M):
    u.unite(X[i]-1,Y[i]-1)
print(u.calc_group_num())

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**7)

def dfs(num,log):
    visited[num]=min(log,visited[num])
    for item in way[num]:
        if visited[item]==10**7:
            dfs(item,log)
    return 

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

visited=[10**7]*N
way=[[] for i in range(N)]
order=[]

for _ in range(M):
    X,Y,Z=map(int,input().split())
    X,Y=min(X,Y),max(X,Y)
    order.append([X-1,Y-1,Z])

order.sort(key=lambda x:(x[0],x[1]))

for item in order:
    way[item[0]].append(item[1])
    way[item[1]].append(item[0])
    
for i in range(N):
    dfs(i,i)

visited=list(set(visited))
print(len(visited))

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):
    x, y, z = map(int, input().split())
    uf.union(x-1, y-1)

print(uf.group_count())

Submission status: Accepted

Solution code:
# union find
def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])


# x,yの属する集合の併合
def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


# xとyが同じグループかどうか判定
def same(x, y):
    return find_root(x) == find_root(y)


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

# 初期化
parent = [i for i in range(n)]  # 根
rank = [1] * n  # 深さ
size = [1] * n  # iを根とするグループのサイズ

# 前処理
edge = [[xyz[m - 1 - i][0] - 1, xyz[m - 1 - i][1] - 1] for i in range(m)]

# 結合後、rootをそれぞれ検索
res = []
for i in range(m):
    unite(edge[i][0], edge[i][1])

arr = [0] * n
for i in range(n):
    arr[i] = find_root(i)
print(len(set(arr)))

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,m = map(int,input().split())
    un = UnionFind(n)
    xyz = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        un.union(xyz[i][0]-1,xyz[i][1]-1)
    ans = 0
    for i in range(n):
        if un.findroot(i) == i:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main() 
    
#endline===============================================

Submission status: Accepted

Solution code:
# ABC126 E 1 or 2

# 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 i in range(M):
    X, Y, Z = map(int, input().split())
    uf.union(X-1, Y-1)

ans = uf.group_count()
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m = map(int, input().split())
xyz=[]
for i in range(m):
    tmp = list(map(int,input().split()))
    xyz.append(tmp)

link = [[] for _ in range(n)]
for tmp in xyz:
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import deque
Q = deque()

from collections import defaultdict
visited = defaultdict(int)
num=0
for i in range(n):
    if visited[i] != 0:
        continue
    num+=1

    Q.append(i)
    visited[i] = num

    while Q:
        now=Q.popleft()
        for nxt in link[now]:
            if visited[nxt] != 0:
                continue
            Q.append(nxt)
            visited[nxt]=num

ans=set()
for v in visited.values():
    ans.add(v)
print(len(ans))

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 unite(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()}
n,m=map(int,input().split())
uf=UnionFind(n)
for i in range(m):
  x,y,z=map(int,input().split())
  uf.unite(x-1,y-1)
print(uf.group_count())

Submission status: Accepted

Solution code:
import sys

# 再帰上限の変更(デフォルトは1000)
# 大きくしすぎるとREするらしい
sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]

# XがわかればYがわかるので、あるAiがわかったときどこまでわかるか?をグラフにしてDFSで探索

graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)

Submission status: Accepted

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

class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)

uft = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    uft.unite(x, y)
group = {uft.find(i) for i in range(1, N+1)}
print(len(group))