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 collections

class UnionFind:
    def __init__(self, n):
        self.par = [k for k 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]:
                #もし二つの木の高さが同じ状態で片方をもう片方に結合すると
                #結合後の木全体の高さは元々より1高くなる
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def tree_count(self):
        l = collections.Counter(self.par[1:])
        return len(l)


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

uf = UnionFind(n)

#print(uf.par)
for i in range(m):
    x,y,z = map(int,input().split())
    uf.union(x,y)
    #print(uf.par)

for j in range(1,n+1):
    _ = uf.find(j)

print(uf.tree_count())

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, nodes):
        self.__parents = {node: None for node in nodes}

    def union(self, a, b):
        root_of_a = self.find(a)
        root_of_b = self.find(b)
        if root_of_a != root_of_b:
            self.__parents[root_of_a] = root_of_b

    def find(self, a):
        if self.__parents[a] is None:
            return a
        root = self.find(self.__parents[a])
        self.__parents[a] = root
        return root

    @property
    def roots(self):
        return set(node for node, parent in self.__parents.items() if parent is None)

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

xyzs = [tuple(map(int, input().split())) for _ in range(m)]

union_find = UnionFind(range(1, n+1))
for x, y, z in xyzs:
    union_find.union(x, y)

print(len(union_find.roots))

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().strip().split(' ')]

a = {}
for i in range(M):
  X, Y, _ = [int(i) for i in input().strip().split(' ')]
  if X not in a: a[X] = set()
  if Y not in a: a[Y] = set()
  a[X].add(Y)
  a[Y].add(X)

len_a = len(a)


def test(key_set):
  tmp = set()
  for key in key_set:
    if key in a:
      tmp = tmp.union(a[key])
      del a[key]

  #print('key_set = {}, tmp = {}'.format(key_set, tmp))
  return tmp


counter = 0
# print(b)

while len(a) > 0:
  #print('---')
  #print('a = {}'.format(a))
  key, key_set = a.popitem()
  #print('key = {}, key_set = {}'.format(key, key_set))
  tmp = test(key_set)
  while len(tmp) > 0:
    tmp = test(tmp)
  #print('a = {}'.format(a))
  counter += 1

print(counter + N - len_a)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, 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):
    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 size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

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

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self._parent = [n for n in range(0, N)]
    self._size = [1] * N

  def find_root(self, 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):
    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 size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x) == self.find_root(y)

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

Submission status: Accepted

Solution code:
class UF():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, 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):
        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 size(self, x):
        return self._size[self.find_root(x)]

    def samegroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
E - 1 or 2
https://atcoder.jp/contests/abc126/tasks/abc126_e

"""
import sys


class DisjointSet(object):
    def __init__(self, n):
        self.rank = [0] * n
        self.p = list(range(n))
        self.size = [1] * n

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.size[self.p[x]] += self.size[self.p[y]]
            self.p[y] = self.findSet(x)
        else:
            self.size[self.p[y]] += self.size[self.p[x]]
            self.p[x] = self.findSet(y)
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

def solve(N, M, hints):
    d = DisjointSet(N+1)
    for x, y, z in hints:
        d.unite(x, y)
    for i in range(1, N+1):
        d.findSet(i)

    ans = set(d.p[1:])
    return len(ans)


def main(args):
    N, M = map(int, input().split())
    hints = [[int(i) for i in input().split()] for _ in range(M)]
    ans = solve(N, M, hints)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
E - 1 or 2
https://atcoder.jp/contests/abc126/tasks/abc126_e

"""
import sys


class DisjointSet:
    def __init__(self, n):
        self.p = list(range(n))

    def root(self, i):
        if self.p[i] == i:
            return i
        else:
            self.p[i] = self.root(self.p[i])
            return self.p[i]

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

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if j >= i:
            self.p[j] = i
        else:
            self.p[i] = j


def solve(N, M, hints):
    d = DisjointSet(N+1)
    for x, y, z in hints:
        d.unite(x, y)
    for i in range(1, N+1):
        d.root(i)

    ans = set(d.p)
    ans.discard(d.p[0])
    return len(ans)


def main(args):
    N, M = map(int, input().split())
    hints = [[int(i) for i in input().split()] for _ in range(M)]
    ans = solve(N, M, hints)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[list(map(int,input().split()))[:2]for i in range(m)]
b=[i for i in range(n+1)]
c=[1]*(n+1)
def root(x):
    if b[x]==x:
        return x
    x=b[x]
    return root(x)
def unite(x,y):
    x=root(x)
    y=root(y)
    if x!=y:
        if c[x]>c[y]:
            b[y]=x
            c[x]+=1
        else:
            b[x]=y
            c[y]+=1
for i,j in a:
    unite(i,j)
for i in range(1,n+1):
    b[i]=root(i)
print(len(set(b[1:])))

Submission status: Accepted

Solution code:
def search(n):
    idx = n
    while A[n-1] != n:
        n = A[n-1]
    A[idx-1] = n

    return n

N, M = list(map(int, input().split()))
A = [i for i in range(1, N+1)]
ans = 0

for i in range(M):
    X, Y, Z = list(map(int, input().split()))
    X_root, Y_root = search(X), search(Y)

    if X_root != Y_root:
        A[X_root-1] = Y_root
        ans += 1

print(N-ans)

Submission status: Accepted

Solution code:
class UnionFind():

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

    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 Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)

        if x == y:
            return False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Size(self, x):
        return -self.root[self.Find_Root(x)]

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

Uni = UnionFind(N)

for i in range(M):
    Uni.Unite(X[i], Y[i])

roots = set()
cnt = 0
for i in range(1, N+1):
    r = Uni.Find_Root(i)
    if r not in roots:
        cnt += 1
        roots.add(r)

print(cnt)

Submission status: Accepted

Solution code:
# Union Find Tree
class UnionFindTree():
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
        self.count = 0

    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i])
            self.parent[i] = group
        return group

    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]:  # rank is same
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px

            self.parent[py] = px
            self.size[px] += self.size[py]
            self.count += 1

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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


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

UFT = UnionFindTree(N)
for x, y, z in A:
    x -= 1
    y -= 1
    UFT.unite(x, y)
print(N - UFT.count)

Submission status: Accepted

Solution code:
from collections import deque

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

checked = [False] * N

edge = [ [] for _ in range(N) ]

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

component = 0

for c , check in enumerate(checked) :
    if check :
        continue

    stack = deque([c])
    component += 1

    while stack :
        current = stack.pop()

        if checked[current] :
            continue

        checked[current] = True
        for v in edge[current] :
            if not checked[v] :
                stack.append(v)

print(component)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        
        self.par = [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 Unite(self, x, y):
        tmpx,tmpy=x,y
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.par[tmpy]  =tmpx

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.par[tmpx]  = tmpy
            # rnkが同じ（深さに差がない場合）は1増やす
            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())
tree=UnionFind(N)

state=[-1]*(N+1)
for i in range(M):
    x,y,z=map(int,input().split())
    tree.Unite(x,y)

memo=[0]*(N+1)

ans=0
for i in range(1,N+1):
    if memo[tree.Find_Root(i)]==0:
        ans+=1
        memo[tree.Find_Root(i)]+=1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]  # 親
		self.rank = [1] * n  # 深さ
		self.size = [1] * n  # size[i]はiを根とするグループのサイズ

	def find(self, x):  # xの親を返す
		if self.par[x] == x:
			return x
		else:
			return self.find(self.par[x])

	def unite(self, x, y):  # x,yの属する集合をマージする
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[x] = y
				self.size[y] += self.size[x]
			else:
				self.par[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

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

uf = UnionFind(N)

for j in range(M):
	uf.unite(X[j] - 1, Y[j] - 1)

roots = set([])
for k in range(N):
	roots.add(uf.find(k))
print(len(roots))

Submission status: Accepted

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

#Union-Find
par=[-1 for i in range(n)]

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

xyz=[]
for i in range(m):
    a=[int(j) for j in input().split()]
    xyz.append([a[0]-1,a[1]-1,a[2]%2])
    if root(a[0]-1)!=root(a[1]-1):
        connect(a[0]-1,a[1]-1)
ans=0
for i in range(n):
    if par[i]<0:
        ans+=1
print(ans)

Submission status: Accepted

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

#Union-Find
par=[-1 for i in range(n)]

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

xyz=[]
for i in range(m):
    a=[int(j) for j in input().split()]
    xyz.append([a[0]-1,a[1]-1,a[2]%2])
    if root(a[0]-1)!=root(a[1]-1):
        connect(a[0]-1,a[1]-1)
ans=0
for i in range(n):
    ans+=1/size(i)
print(round(ans))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n)
    self.rnk=[0]*(n)
    
  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 Unite(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
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y]+=1
        
  def isSameGroup(self,x,y):
    return self.Find_Root(x) == self.Find_Root(y)
  
  def Count(self,x):
    return -self.root[self.Find_Root(x)]


uf=UnionFind(n)
for iii in range(m):
  x,y,z=map(int,input().split())
  x-=1
  y-=1
  uf.Unite(x,y)

cnt=0
for iii in uf.root:
  if iii<0:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rnk=[0]*(n+1)
    
  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 Unite(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
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y]+=1
        
  def isSameGroup(self,x,y):
    return self.Find_Root(x) == self.Find_Root(y)
  
  def Count(self,x):
    return -self.root[self.Find_Root(x)]


uf=UnionFind(n)
for iii in range(m):
  x,y,z=map(int,input().split())
  uf.Unite(x,y)

cnt=0
for iii in uf.root:
  if iii<0:
    cnt+=1
print(cnt-1)

Submission status: Accepted

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

    # 検索
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        d1=self.par[x]
        d2=self.par[y]
        if d1<=d2:
            self.par[y]=x
            self.sizes[x]=self.sizes[x]+self.sizes[y]
            if d1==d2:
                self.par[x]=self.par[x]-1
        else:
            self.par[x]=y
            self.sizes[y]=self.sizes[x]+self.sizes[y]

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    #サイズ
    def size(self,x):
        return self.sizes[find(x)]

    #木の数
    def number(self):
        count=0
        for i in self.par[1:]:
            if i<0:
                count=count+1
        return count
        
N,M=map(int,input().split())
U=UnionFind(N)
for i in range(M):
    X,Y,Z=map(int,input().split())
    U.union(X,Y)
print(U.number())

Submission status: Accepted

Solution code:
#UnionFindクラス
class UnionFind(object):
 
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.size=[1 for i in range(n)]
 
    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 x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x]+=self.size[y]
            
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def tree_size(self,x):
        return self.size[self.find(x)]
    
def main():
    n,m = map(int, input().split())
    uf = UnionFind(n)
    for i in range(m):
        x, y, z = map(int, input().split())
        x -= 1
        y -= 1
        if not uf.same(x,y):
            uf.union(x,y)
    res = 0
    for i in range(n):
        if uf.par[i] == i:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if self.rank[xRoot] > self.rank[yRoot]:
            self.parent[yRoot] = xRoot
        elif self.rank[xRoot] < self.rank[yRoot]:
            self.parent[xRoot] = yRoot
        elif xRoot != yRoot:
            self.parent[yRoot] = xRoot
            self.rank[xRoot] += 1
        # print(x, y, xRoot, yRoot, self.parent)

    def num_disjoint_set(self):
        return len(set([self.find(i) for i in range(n)]))


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

dset = DisjointSet(n)

for x, y, _ in g:
    dset.union(x - 1, y - 1)

print(dset.num_disjoint_set())

Submission status: Accepted

Solution code:
import sys
mod = 10**9+7
sys.setrecursionlimit(mod)
N,M=map(int, input().split())

adj={i: set() for i in range(1,N+1)}
for i in range(M):
  x,y,z=map(int, input().split())
  adj[x].add(y)
  adj[y].add(x)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    for u in adj[v]: dfs(u)
cnt=0
for i in range(1,N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

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

cost = 0
for i in range(N):
	if c[i] == 0:
		cost += 1
		q.append(i)
		while len(q):
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 126
# https://atcoder.jp/contests/abc126
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    XYZ = ii2nnn(M)
    G = [[] for _ in range(N)]
    for x, y, z in XYZ:
        G[x-1].append(y-1)
        G[y-1].append(x-1)
    S = set()
    c = 0
    for i in range(N):
        if i in S:
            continue
        c += 1
        S.add(i)
        q = [i]
        while len(q) > 0:
            j = q.pop()
            for k in G[j]:
                if k in S:
                    continue
                S.add(k)
                q.append(k)
    print(c)

main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(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
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            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())

bridge = [tuple(map(int, input().split())) for _ in range(M)]

ins = UnionFind(N)

for i in range(M):
    ins.union(bridge[M-1-i][0],bridge[M-1-i][1])

ans = 0

for i in range(1,N+1):
    if ins.find(i) == i:
        ans = ans + 1

print(ans)

Submission status: Accepted

Solution code:
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_not(self,x,y):
        return self.findroot(x) == self.findroot(y)

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)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
adj = {u: [] for u in range(1, N+1)}
for i in range(M):
    X, Y, Z = map(int, input().split())
    adj[X].append(Y)
    adj[Y].append(X)

remain = set(adj.keys())

ncc = 0  # the number of connected components
while len(remain) > 0:
    head = remain.pop()
    remain.add(head)  # push back
    queue = deque()
    queue.append(head)
    while len(queue) > 0:
        u = queue.popleft()
        if u not in remain:
            continue
        remain.remove(u)
        queue.extend(adj[u])
    ncc += 1

print(ncc)

Submission status: Accepted

Solution code:
#coding:utf-8
# https://reiyw.com/post/union-find-tree-in-python/
import collections
import itertools
import operator
class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            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 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 are_same(self, x, y):
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

N,M=map(int,raw_input().split())
uf=UnionFind(range(1,N+1))
for i in range(M):
    x,y,z=map(int,raw_input().split())
    uf.unite(x,y)

from collections import defaultdict
F=set()
for i in range(1,N+1):
    F.add(uf.find(i))
print(len(F))

Submission status: Accepted

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


def search(UF,loc):
    if UF[loc] == loc:
        return UF[loc]
    else:
        UF[loc] = search(UF,UF[loc])
        return UF[loc]
    
dic = [0]*(n+1)
A = [0]*(n+1)
UF = [_ for _ in range(n+1)]
for x,y,z in XYZ:
    UF[x] = search(UF,x)
    UF[y] = search(UF,y)
    if UF[x] != UF[y]:
        UF[max(UF[x],UF[y])] = min(UF[x],UF[y])


for i in range(1,n+1):
    temp = search(UF,i)
    dic[temp] = 1
print(sum(dic))

Submission status: Accepted

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

xy = [i for i in range(n + 1)]


def root(x):
    i = x
    while i != xy[i]:
        i = xy[i]
    xy[x] = i
    return i


for _ in range(m):
    x, y = map(int, input().split()[:2])
    xy[root(x)] = root(y)

print(sum(i == v for i, v in enumerate(xy)) - 1)

Submission status: Accepted

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

xy = [i for i in range(n + 1)]


def root(x):
    i = x
    a = []
    while i != xy[i]:
        i = xy[i]
        a += [i]
    for b in a:
        xy[b] = i
    return i


for _ in range(m):
    x, y = map(int, input().split()[:2])
    xy[root(x)] = root(y)

ans = sum(i == v for i, v in enumerate(xy)) - 1

print(ans)

Submission status: Accepted

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

xy = [i for i in range(n + 1)]


def root(x):
    i = x
    while i != xy[i]:
        i = xy[i]
    xy[x] = i
    return i


for _ in range(m):
    x, y = map(int, input().split()[:2])
    rx = root(x)
    ry = root(y)
    if rx < ry:
        xy[rx] = ry
    else:
        xy[ry] = rx

ans = sum(i == v for i, v in enumerate(xy)) - 1

print(ans)

Submission status: Accepted

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

xy = [i for i in range(n + 1)]


def root(x):
    i = x
    while i != xy[i]:
        i = xy[i]
    xy[x] = i
    return i


for _ in range(m):
    x, y = map(int, input().split()[:2])
    xy[root(x)] = root(y)

ans = sum(i == v for i, v in enumerate(xy)) - 1

print(ans)

Submission status: Accepted

Solution code:
def solve(n, m, x, y, z):
    parent = {i: i for i in range(1, n+1)}
    def find(v):
        if v == parent[v]:
            return v
        else:
            return find(parent[v])
    def union(u, v):
        u = find(u)
        v = find(v)
        if u > v:
            u, v = v, u
        parent[v] = u
    for i in range(m):
        union(x[i], y[i])
    return len(set([find(v) for v in parent.keys()]))

n, m = map(int, input().split())
x = [0] * m
y = [0] * m
z = [0] * m
for i in range(m):
    x[i], y[i], z[i] = map(int, input().split())
print(solve(n, m, x, y, z))