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

Solution (Python):
class UnionFindTree:
    __slots__ = ('__tree', '__current')

    def __init__(self, n):
        self.__tree = [-1] * n
        self.__current = iter(self.__tree)

    def find(self, x):
        t = self.__tree
        if t[x] < 0:
            return x
        root = self.find(t[x])
        t[x] = root
        return root

    def union(self, x, y):
        t = self.__tree
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if t[x] > t[y]:
            x, y = y, x
        t[x] += t[y]
        t[y] = x
        return True

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

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

    def __next__(self):
        try:
            return next(self.__current)
        except StopIteration:
            self.__current = iter(self.__tree)
            raise StopIteration()

    def __iter__(self):
        return self


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m = spline()
    tree = UnionFindTree(n)
    for i in range(1, m + 1):
        x, y, _ = spline(func_=lambda x: int(x) - 1)
        tree.union(x, y)
    ans = 0
    for i in tree:
        if i < 0:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
class UnionFindTree:
    __slots__ = ('__tree', '__current')

    def __init__(self, n):
        self.__tree = [-1] * n
        self.__current = iter(self.__tree)

    def find(self, x):
        t = self.__tree
        if t[x] < 0:
            return x
        root = self.find(t[x])
        t[x] = root
        return root

    def union(self, x, y):
        t = self.__tree
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if t[x] > t[y]:
            x, y = y, x
        t[x] += t[y]
        t[y] = x
        return True

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

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

    def __next__(self):
        try:
            return next(self.__current)
        except StopIteration:
            self.__current = iter(self.__tree)
            raise StopIteration()

    def __iter__(self):
        return self


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m = spline()
    tree = UnionFindTree(n)
    for i in range(1, m + 1):
        x, y, _ = spline()
        x -= 1
        y -= 1
        tree.union(x, y)
    ans = 0
    for i in tree:
        if i < 0:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


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

    
    def Find(self, x):
        
        if self.par[x] < 0:
            return x
        
        
        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 False
        
        if (self.par[x]>self.par[y]):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True
    
    def isSameGroup(self, x, y):
        return self.Find(x)==self.Find(y)
    
    def Size(self, x):
        return self.par[self.Find(x)]*-1

    def Show(self):
        return self.par

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
    uf.Union(x, y)

ans = 0
for i in uf.Show():
    if i<0:
        ans += 1

print(ans)

Solution (Python):
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))

global par
par=[-1 for i in range(100001)]

def find(u):
    if(par[u]<0):
        return u
    else:
        return find(par[u])
def uni(x,y):
    u=find(x)
    v=find(y)
    if u==v:
        return
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[v]=u
    else:    
        par[v]+=par[u]
        par[u]=v
t=1
for term in range(1,t+1):
    n,m=rd(2)
    for i in range(m):
        x,y,z=rd(2)
        uni(x,y)
        
    ans=0
    for i in range(1,n+1):
        if(par[i]<0):
            ans+=1
    
    print(ans)

Solution (Python):
N,M = map(int,input().split())
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())
uf = UnionFind(N)
for i in range(M):
  x,y,z=map(int,input().split())
  uf.union(x-1,y-1)
print(uf.group_count())

Solution (Python):
from collections import deque
n, m = map(int, input().split())
tree = [[] for i in range(n)]

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

already = [False]*n
ans = 0
for i in range(n):
  if already[i]:
    continue
  ans += 1
  not_yet = deque(tree[i])
  for value in tree[i]:
    already[value] = True
  while not_yet:
    key = not_yet.popleft()
    for value in tree[key]:
      if already[value]:
        continue
      already[value] = True
      not_yet.append(value)
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(1000000)

def main():
    n, m = map(int, input().split())
    parents = [i for i in range(n)]
    for i in range(m):
        x, y, z = map(int, sys.stdin.readline().split())
        unite(x - 1, y - 1, parents)
    uniq = {find(i, parents) for i in range(n)}
    print(len(uniq))

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

def find(x, parents):
    if parents[x] == x:
        return x
    fx = find(parents[x], parents)
    parents[x] = fx
    return fx

if __name__ == "__main__":
    main()

Solution (Python):


import sys
sys.setrecursionlimit(1000000)

def main():
    n, m = map(int, input().split())
    parents = [i for i in range(n)]
    for i in range(m):
        x, y, z = map(int, input().split())
        unite(x - 1, y - 1, parents)
    uniq = {find(i, parents) for i in range(n)}
    print(len(uniq))

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

def find(x, parents):
    if parents[x] == x:
        return x
    fx = find(parents[x], parents)
    parents[x] = fx
    return fx

if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
    
root=[int(i) for i in range(n)] 
rank=[0]*n    
def find(x):
    if root[x]==x:
        return x 
    else:
        return find(root[x])

for i in range(m):
    x,y,z=map(int,input().split())
    fx=find(x-1)
    fy=find(y-1)
    if rank[fx]>=rank[fy]:
        root[fy]=fx
        if rank[fx]==rank[fy]:
            rank[fx]+=1
    else:
        root[fx]=fy 
a=[]
for i in range(n):
    a.append(find(i)) 
print(len(set(a)))

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

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

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
 
    def find(self, x):
        """
        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 と 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 is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
 
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


uf = UnionFind(N)
for j in range(M):
    x, y, z = list(map(int, input().split()))
    if not uf.is_same(x-1, y-1):
        uf.union(x-1, y-1)


ans = 0
for i in range(N):
    if i == uf.par[i]:
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)

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

UF = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    x, y = x-1, y-1
    UF.merge(x, y)

UF.updatePars()

ans = len(set(UF.pars))
print(ans)

Solution (Python):
from collections import Counter


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ 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 is_same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        x = self.find(x)
        return self.size[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)

c = Counter([uf.find(i) for i in range(n)])
print(len(c))

Solution (Python):
class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
        self.u = n

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

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

        self.u -= 1

        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x

        return True

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

    def size(self, x):
        return -self.d[self.root(x)]

    def num_union(self):
        return self.u


N, M, *X = map(int, open(0).read().split())
X = tuple(zip(*[iter(X)]*3))

uf = UnionFind(N)
for x, y, z in X:
    uf.unite(x-1, y-1)

print(uf.num_union())

Solution (Python):
import sys

n, m = map(int, sys.stdin.readline().split())

root = list(range(n))
height = [0] * n
size = [1] * n

def find_root(u):
  if root[u] == u: return u
  root[u] = find_root(root[u])
  return root[u]

def unite(u, v):
  ru = find_root(u)
  rv = find_root(v)
  if ru == rv: return
  if height[ru] >= height[rv]:
    root[rv] = ru
    size[ru] += size[rv]
    height[ru] = max(height[ru], height[rv] + 1)
  else:
    root[ru] = rv
    size[rv] += size[ru]

def main():
  for _ in range(m):
    x, y, z = map(int, sys.stdin.readline().split())
    unite(x-1, y-1)
  
  for i in range(n): find_root(i)
  print(len(set(root)))
  
if __name__ == '__main__':
  main()

Solution (Python):
import sys

n, m = map(int, sys.stdin.readline().split())

root = list(range(n))
height = [0] * n
size = [1] * n

def find_root(u):
  if root[u] == u: return u
  root[u] = find_root(root[u])
  return root[u]

def unite(u, v):
  ru = find_root(u)
  rv = find_root(v)
  if ru == rv: return
  if height[ru] >= height[rv]:
    root[rv] = ru
    size[ru] += size[rv]
    height[ru] = max(height[ru], height[rv] + 1)
  else:
    root[ru] = rv
    size[rv] += size[ru]

def main():
  for _ in range(m):
    x, y, z = map(int, sys.stdin.readline().split())
    unite(x-1, y-1)
  
  for i in range(n): find_root(i)
  print(len(set(root)))
  
if __name__ == '__main__':
  main()

Solution (Python):
import collections, math, bisect

local = False
if local:
    file = open("input.txt", "r")
    import time

def inp():
    if local:
        return file.readline().rstrip()
    else:
        return input().rstrip()

def ints():
    return [int(_) for _ in inp().split()]


if local:
    start=time.time()

N,M = ints()

connection = [dict() for i in range(N)]

for i in range(1, M+1):
    x,y,z = ints()

    connection[x-1][y-1] = True
    connection[y-1][x-1] = True

ans = 0
visited = set()

for i in range(N):
    if i in visited:
        continue

    ans+=1
    stck = [i]
    visited.add(i)

    while len(stck)>0:
        vertex = stck.pop(-1)

        for nextVertex in connection[vertex]:
            if nextVertex not in visited:
                visited.add(nextVertex)
                stck.append(nextVertex)

print(ans)


if local:
    fin = (time.time()-start)*1000
    print("{:.2f}".format(fin) + "ms")

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parent=list(range(n+1))
        self.size=[1]*(n+1)
    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 x==y:
            return
        else:
            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 cnt(self,x):
    
        return self.size[self.find(x)]

def main():
    n,m=map(int,input().split())
    u=UnionFind(n)
    for i in range(m):
        x,y,z=map(int,input().split())
        u.unite(x,y)
    ans=[0]*(n+1)
    for i in range(1,n+1):
        x=u.find(i)
        ans[x]=1
    print(sum(ans[1:]))

if __name__ == '__main__':
    main()

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()


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

  def unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return False
    if self.data[x]>self.data[y]:
      x,y=y,x
    self.data[x]+=self.data[y]
    self.data[y]=x
    return True

  def find(self,k):
    if self.data[k]<0:
      return k
    self.data[k]=self.find(self.data[k])
    return self.data[k]

  def size(self,k):
    return -self.data[self.find(k)]


def main():
  n,m=LI()
  uf=UnionFind(n)
  for _ in range(m):
    a,b,c=LI()
    a-=1
    b-=1
    uf.unite(a,b)

  checked=[False]*n
  ans=0
  for i in range(n):
    a=uf.find(i)
    if checked[a]==False:
      checked[a]=True
      ans+=1

  return ans


print(main())

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


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())

      
uf = UnionFind(N + 1)

for _ in range(M):
  X, Y, Z = map(int, input().split())
  uf.union(X, Y)
  
  
print(uf.group_count() - 1)

Solution (Python):
def find(x):
    if x == par[x]:
        return x
    par[x] = find(par[x])
    return par[x]
 
def union(x,y):
    x,y = find(x),find(y)
    if x == y:
        return
    par[y] = x
 
n,m = map(int,input().split())
par = {i:i for i in range(1,n+1)}
for _ in range(m):
    a,b,c = map(int,input().split())
    union(a,b)
print(sum([1 for i in range(1,n+1) if par[i] == i]))

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


def find(A,x):
    p = A[x]
    if p == x: return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[by] = bx 

N, M = lr()
V = [x for x in range(N+1)]
for _ in range(M):
    x, y, z = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)

V = [find(V, x) for x in V]
s = set(V[1:])
answer = len(s)
print(answer)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [1 for i in range(N)]

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

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

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    for i in range(M):
        a, b, _ = (int(i)-1 for i in input().split())
        unite(a, b)
    ans = set()
    for i in range(N):
        ans.add(find_root(i))
    print(len(ans))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

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

G = [[] for _ in range(N + 1)]
for el in XYZ:
    x, y, z = el
    G[x].append(y)
    G[y].append(x)

seen=[False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)

cnt = 0
for start in range(1, N + 1):
    if seen[start] == False:
        dfs(start)
        cnt += 1
print(cnt)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())

    uf = UnionFindTree(N)
    for _ in range(M):
        x,y,z=map(int, input().split())
        uf.union(x-1,y-1)
    c=set([uf.find(i) for i in range(N)])
    print(len(c))


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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * size
        self.rank = [1] * size
        self.groups = size

    def get_root(self, node):
        parent = self.parent[node]
        if parent == -1:
            root = node
        else:
            root = self.get_root(parent)
            self.parent[node] = root  
        return root

    def in_same_group(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        return root1 == root2

    def unite(self, node1, node2):
        if self.in_same_group(node1, node2):
            return
        main_root = self.get_root(node1)
        sub_root = self.get_root(node2)
        if self.rank[main_root] < self.rank[sub_root]:
            main_root, sub_root = sub_root, main_root

        self.parent[sub_root] = main_root
        self.rank[main_root] += self.rank[sub_root]
        self.groups -= 1


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
    uf.unite(x, y)

print(uf.groups)

Solution (Python):
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 k in range(M):
    X, Y, Z = map(int,input().split())
    uf.union(X-1,Y-1)
print(uf.group_count())

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

s = []
visit = [-1]*n
cnt = 0
for i in range(n):
    if visit[i] == -1:
        s.append(i)
        cnt += 1
        visit[i] = cnt
        while s:
            v = s.pop()
            for u in g[v]:
                if visit[u] == -1:
                    visit[u] = visit[v]
                    s.append(u)
print(max(visit))

Solution (Python):
class UnionFindTree:
    def __init__(self, n):
        self.par = [-1 for _ in range(n)]
        
    def find(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
        
    def size(self, x):
        return -self.par[self.find(x)]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.size(x) < self.size(y):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return 1
        
n, m = map(int, input().split())
uf = UnionFindTree(n)
ans = n
for _ in range(m):
    x, y, z = map(int, input().split())
    ans -= uf.unite(x-1, y-1)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
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 _ in range(M):
  x, y, z = map(int, input().split())
  uf.Unite(x, y)

roots = set()
for i in range(1, N + 1): roots.add(uf.Find_Root(i))
print(len(roots))

Solution (Python):
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

for _ in range(M):
    fr, to, _ = map(int, input().split())
    tree.union(fr - 1, to - 1)

print(tree.getComponent())

Solution (Python):
N,M = map(int,input().split())
XYZ = [tuple(map(int,input().split())) for i in range(M)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]
uf = UnionFind(N)
for x,y,_ in XYZ:
    x,y = x-1,y-1
    if uf.is_same(x,y): continue
    uf.unite(x,y)
print(N - uf.count)