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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200000)

def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(M):
        conn[X[i] - 1].append(Y[i] - 1)
        conn[Y[i] - 1].append(X[i] - 1)

    def dfs(idx, conn, visited):
        visited[idx] = True
        for c in conn[idx]:
            if not visited[c]:
                dfs(c, conn, visited)
        return visited

    visited = [False] * N
    ret = 0
    for i in range(N):
        if not visited[i]:
            visited = dfs(i, conn, visited)
            ret += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]" 
    Y = [int()] * (M)  # type: "List[int]" 
    Z = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

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

Submission status: Accepted

Solution code:
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,M=map(int,input().split())
G=UnionFind(N)
for i in range(M):
    x,y,z=map(int,input().split())
    G.unite(x-1,y-1)
X=[G.find(i) for i in range(N)]
print(len(set(X)))

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10 ** 6)
 
class UnionFind():
	def __init__(self, size):
		self.length = size
		self.table = [-1 for _ in range(size)]
		self.size = [1 for _ in range(size)]
 
	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]
 
	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
 
		return

	def get_size(self):
		cnt = 0
		for i in range(self.length):
			if self.table[i] < 0:
				cnt += 1
		return cnt

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

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

print(uf.get_size())

Submission status: Accepted

Solution code:
N,M=list(map(int,input().strip().split(' ')))
graph=[[]  for i in range(N+1)]
for _ in range(M):
    a,b,c=list(map(int,input().strip().split(' ')))
    graph[a]+=[b]
    graph[b]+=[a]

checked={}
def dfs(root):
    connected=[]
    stack=[]
    stack+=[root]
    parent={}
    parent[root]=-1
    checked[root]=1
    while stack:
        v=stack.pop()
        for node in graph[v]:
            if node!=parent[v] and node not in checked:
                checked[node]=1
                parent[node]=v
                stack+=[node]
    return stack
count=0
for i in range(1,N+1):
    if i not in checked:
        dfs(i)
        count+=1
print(count)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    s = input()
    for i in range(k-1):
        print(s[i],end = "")
    print(s[k-1].lower(),end = "")
    for i in range(k,n):
        print(s[i],end = "")
    print()
    return

#B
def B():
    s = S()
    k = int(s[0])*10+int(s[1])
    l = int(s[2])*10+int(s[3])
    if k == 0:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")
    elif k < 13:
        if l == 0:
            print("MMYY")
        elif l < 13:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    else:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")

#C
def C():
    n,k = LI()
    ans = 0
    for i in range(1,n+1):
        l = k/i
        ans += 1/n*1/(2 << max(0,math.ceil(math.log(l,2))))
    print(ans*2)
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y,w = LI()
        x -= 1
        y -= 1
        v[x].append((y,w))
        v[y].append((x,w))
    ans = [0 for i in range(n)]
    bfs_map = [1 for i in range(n)]
    bfs_map[0] = 0
    q = deque()
    q.append(0)
    while q:
        x = q.popleft()
        for y,w in v[x]:
            if bfs_map[y]:
                if w%2:
                    ans[y] = ans[x]^1
                else:
                    ans[y] = ans[x]
                bfs_map[y] = 0
                q.append(y)
    for i in ans:
        print(i)
    return

#E
def E():
    def root(x):
        if par[x] == x:
            return par[x]
        par[x] = root(par[x])
        return par[x]
    def same(x,y):
        return root(x) == root(y)
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    for i in range(m):
        x,y,z = LI()
        x -= 1
        y -= 1
        if not same(x,y):
            unite(x,y)
    for i in range(n):
        root(i)
    par = list(set(par))
    print(len(par))
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    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,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  # 親が同じかみる
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
tree = Unionfindtree(N)
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    tree.union(a,b)
H=set()
for i in range(N):
    s=tree.find(i)
    if s not in H:
        H.add(s)
    #print(s)
print(len(H))

Submission status: Accepted

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

class mergefind:
    def __init__(self,n):
        self.parent = list(range(n))
        self.size = [1]*n
        self.num_sets = n

    def find(self,a):
        to_update = []
       
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
       
        for b in to_update:
            self.parent[b] = a

        return self.parent[a]

    def merge(self,a,b):
        a = self.find(a)
        b = self.find(b)

        if a==b:
            return

        if self.size[a]<self.size[b]:
            a,b = b,a

        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets

n,m = [int(x) for x in input().split()]

dsu = mergefind(n)
for _ in range(m):
    a,b,c = [int(x) for x in input().split()]
    dsu.merge(a-1,b-1)

print len(dsu)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Tree=[i for i in range(N)]
size=[1]*N
 
def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
    size[s1]+=size[s2]
ans=N
for i in range(M):
  X,Y,Z=map(int,input().split())
  X,Y=X-1,Y-1
  if find(X)!=find(Y):
    unite(X,Y)
    ans-=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline
n,m = map(int,input().split())
ans = []
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return
Uni = UnionFind(n)
for i in range(m):
    x,y,z = map(int,input().split())
    x-=1;y-=1
    Uni.union(x,y)

for i in range(n):
    ans.append(Uni.find(i))
print(len(set(ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*10**6)
class UF():
    def __init__(self, num):
        self.par = [-1]*num
        self.size = [1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.size[rx] += self.size[ry] 
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.size[ry] += self.size[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.size[rx] += self.size[ry]
        return

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx == ry:
        return False
    if uf[rx] > uf[ry]:
        rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

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 uf[i] < 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        p[py] = px
    else:
        p[px] = py
*p, = range(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 root(i) == i:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)


if __name__ == "__main__":
    N,M=[int(i) for i in input().strip().split(" ")]
    node_list = [UnionFindNode(i) for i in range(N)]
    import sys
    for line in sys.stdin:
        x,y,z=[int(i) for i in line.strip().split(" ")]
        x -= 1
        y -= 1
        node_list[x].unite(node_list[y])
    counter = 0
    for node in node_list:
        if not node.parent_:
            counter += 1
    print(counter)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,m = LI()
    aa = [LI_() for _ in range(m)]
    uf = UnionFind(n)
    for a,b,c in aa:
        uf.union(a,b)
    r = 0
    for i in range(n):
        if uf.table[i] < 0:
            r += 1

    return r


print(main())

Submission status: Accepted

Solution code:
import sys


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

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

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n, m = map(int, input().split())
uft = UnionFind(n)
for line in sys.stdin:
    x, y, z = map(int, line.split())
    x -= 1
    y -= 1
    uft.union(x, y)

ans = 0
for v in uft.table:
    if v < 0:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
par = [i for i in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
for i in range(Q):
    x,y,z=map(int,input().split())
    unite(x,y)
    
for i in range(1,N+1):
    find(i)
print(len(set(par[1:])))

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
par = [i for i in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
for i in range(Q):
    x,y,z=map(int,input().split())
    unite(x,y)
    
for i in range(1,Q+1):
    find(i)
print(len(set(par[1:])))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

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

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

        self.par[x]=self.find(self.par[x])
        return self.par[x]

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

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

        self.grp-=1
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def group_num(self):
        return self.grp



n,m=map(int,input().split())
uf=UnionFind(n)
ans=chk=0
w=collections.deque()
for i in range(m):
    x,y,z=map(int,input().split())
    uf.unite(x,y)
print(uf.group_num)

Submission status: Runtime Error

Solution code:
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])

    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


import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

n, m = map(int, input().split())
u = UnionFind(n)
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    u.Unite(a, b)
print(len(set(u.Find_Root(i) for i in range(n))))

Submission status: Runtime Error

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

from mymodules.somedatastrs import UnionFind

n, m = [int(x) for x in input().split()]
A = UnionFind(n)
ans = n
for i in range(m):
    x, y, _ = [int(z) - 1 for z in input().split()]
    if not A.samegrp(x, y):
        ans -=1
    A.union(x, y)

print(ans)

Submission status: Runtime Error

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

par=[i for i in range(n)]


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


def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy


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

ans=0

for i in range(n):
    if i==find(i):
        ans+=1

print(ans)

Submission status: Runtime Error

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

par=[i for i in range(n)]

visited=[False]*n

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


def find2(x):
  visited[x]=True
  if par[x]==x:
    return par[x]
  else:
    par[x]=find2(par[x])
    return par[x]

def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy

ans=-1

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

cnt=0

for i in range(n):
  if visited[i]==False:
    cnt+=1
    find2(i)


ans=min(cnt,len(set(par)))


print(ans)

Submission status: Runtime Error

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

par=[i for i in range(n)]

visited=[False]*n

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


def find2(x):
  visited[x]=True
  if par[x]==x:
    return par[x]
  else:
    par[x]=find2(par[x])
    return par[x]

def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy

ans=-1

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

cnt=0

for i in range(n):
  if visited[i]==False:
    cnt+=1
    find2(i)


ans=min(cnt,len(set(par)))


print(ans)

Submission status: Runtime Error

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

par=[i for i in range(n)]

visited=[False]*n

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


def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy

ans=-1

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


ans={find(i) for i in range(n)}

print(len(ans))

Submission status: Runtime Error

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

par=[i for i in range(n)]

visited=[False]*n

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


def find2(x):
  visited[x]=True
  if par[x]==x:
    return par[x]
  else:
    par[x]=find2(par[x])
    return par[x]

def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy

ans=-1

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

ans=1

for i in range(n):
  if visited[i]==False:
    ans+=1
    find2(i)

print(min(ans,len(set(par))))

Submission status: Runtime Error

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

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:
        continue
    par[x] = y
    size[y] += size[x]
    size[x] = 0

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

Ans =0
for j in size[1:]:
    if j != 0:
        Ans +=1
print(Ans)

Submission status: Runtime Error

Solution code:
import collections

N, M = map(int, input().split())
par = [i for i in range(N+1)]

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 0
    par[x] = y

for i in range(M):
    X, Y, Z = map(int, input().split())
    unite(X, Y)
    print(par)

res = par[1:]
c = collections.Counter(res)
print(len(c))

Submission status: Runtime Error

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

flag=list(range(N))
def takeflag(p):
    stock=[]
    while flag[flag[p]]!=flag[p]:
        stock.append(p)
        p=flag[p]
    p=flag[p]
    for i in stock:
        flag[i]=p
    return p

for i in range(M):
    x,y,z = map(int,input().split())
    x,y = map(takeflag,(x,y))
    x,y = min(x,y),max(x,y)
    flag[x]=y

st=set()
for i in range(N):
    st.add(takeflag(i))

print(len(st))

Submission status: Runtime Error

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

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

class Union_Find:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for i in range(n)]
    
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
    
    def unite(self, x, y):
        if self.rank[x] == self.rank[y]:
            self.parent[y] = x
            self.rank[x] += 1
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y

uftree = Union_Find(N+1)

for i in range(M):
    x, y, _ = map(int, input().split())
    uftree.unite(x, y)

result = 0
for i in range(1, N+1):
    if uftree.find(i) == i:
        result += 1

print(result)

Submission status: Runtime Error

Solution code:
import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
sys.setrecursionlimit(10**9)

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

class Union_Find:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for i in range(n)]
    
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
    
    def unite(self, x, y):
        if self.rank[x] == self.rank[y]:
            self.parent[y] = x
            self.rank[x] += 1
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y

uftree = Union_Find(N+1)

for i in range(M):
    x, y, _ = map(int, input().split())
    uftree.unite(x, y)

result = 0
for i in range(1, N+1):
    if uftree.find(i) == i:
        result += 1

print(result)

Submission status: Runtime Error

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

class Union_Find:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for i in range(n)]
    
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
    
    def unite(self, x, y):
        if self.rank[x] == self.rank[y]:
            self.parent[y] = x
            self.rank[x] += 1
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y

uftree = Union_Find(N+1)

for i in range(M):
    x, y, _ = map(int, input().split())
    uftree.unite(x, y)

result = 0
for i in range(1, N+1):
    if uftree.find(i) == i:
        result += 1

print(result)

Submission status: Runtime Error

Solution code:

N, M = map(int, input().split())
XYZs = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

groups = [-1 for _ in range(N)]
connections = set()

now = 0
for XYZ in XYZs:
    if groups[XYZ[0]] == -1 and groups[XYZ[1]] == -1:
        now += 1
        groups[XYZ[0]] = now
        groups[XYZ[1]] = now
    elif groups[XYZ[0]] == -1:
        groups[XYZ[0]] = groups[XYZ[1]]
    elif groups[XYZ[1]] == -1:
        groups[XYZ[1]] = groups[XYZ[0]]
    elif groups[XYZ[0]] != groups[XYZ[1]]:
        if groups[XYZ[0]] > groups[XYZ[1]]:
            connections.add(str(groups[XYZ[1]])+"-"+str(groups[XYZ[0]]))
        else:
            connections.add(str(groups[XYZ[0]])+"-"+str(groups[XYZ[1]]))

print(connections)

answer = 0
for i in range(N):
    if groups[i] == -1:
        answer+=1
connections_list = []
for connection in connections:
    connections_list.append(list(map(int,connection.split("-"))))

connections_list = sorted(connections_list)
groups_set = set([i for i in range(now)])

for connection in connections_list:
    groups_set.remove(connection[0])

print(answer+len(groups_set))