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:
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]

    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
N,M = map(int,input().split())
u = UnionFind(N)
for i in range(M):
    X,Y,Z = map(int,input().split())
    u.union(X-1,Y-1)
ans = []
for i in range(N):
    ans.append(u.find(i))
ans = len(set(ans))
print(ans)

Submission status: Accepted

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

n, m = [int(i) for i in input().split()]
U = [[int(i) for i in input().split()] for j in range(m)]

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

for u, v, w in U:
    E[u].append(v)
    E[v].append(u)

visited = [False] * (n + 1)

def dfs(v):
    if visited[v]:
        return 0
    
    visited[v] = True

    for e in E[v]:
        dfs(e)
    
    return 1

ans = 0

for i in range(1, n + 1):
    ans += dfs(i)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

n, m = map(int, raw_input().strip().split())
inp = stdin.readlines()

g = [[] for i in xrange(n + 1)]

for line in inp:
    x, y, z = map(int, line.strip().split())
    g[x].append(y)
    g[y].append(x)

vis = [0] * (n + 1)

def bfs(root):
    global vis
    
    vis[root] = 1
    q = deque([root])
    while q:
        u = q.popleft()
        for v in g[u]:
            if not vis[v]:
                vis[v] = 1
                q.append(v)
    
ans = 0
for u in xrange(1, n + 1):
    if vis[u] == 0:
        bfs(u)
        ans += 1

print ans

Submission status: Accepted

Solution code:
class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

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

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

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True


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

uni = Union(N)

for x,y,z in XYZ:
  uni.merge(x - 1, y - 1)

Ans = 0
for i in uni.T:
  if i < 0:
    Ans += 1

print(Ans)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

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

    def componentNum(self):
        ret = 0
        for i in range(N):
            if self.parent[i] == i:
                ret += 1
        return ret


sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

for x, y, z in hint:
    Un.union(x, y)
comp = Un.componentNum()
print(comp)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1]*size #非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
        
        
n,m = [int(i) for i in input().split()]

T=UnionFind(n)
c=0
for _ in [0]*m:
    x,y,z=[int(i) for i in input().split()]
    if not T.issame(x-1,y-1):
        T.merge(x-1,y-1)
        c+=1

print(n-c)

Submission status: Accepted

Solution code:
#ABC094-E
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,m=IL()
#Union-Find木
par=[]
rank=[]
def init(a): #初期化
    for i in range(a):
        par.append(i)
        rank.append(0)
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 rank[x]==rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1
    return
def same(x,y): #同じ集合か判定
    return find(x)==find(y)

init(n)
gn=n
for i in range(m):
    x,y,z=IL()
    if find(x-1)!=find(y-1):
        n-=1
        unite(x-1,y-1)
print(n)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
xyz= [list(map(int,input().split())) for _ in [0]*M]
par = [-1]*N
def get_parent(n):
    if par[n]==-1:return n
    else:
        par[n] = get_parent(par[n])
        return par[n]
def merge(i,j):
    i = get_parent(i)
    j = get_parent(j)
    if i!=j:par[j] = i
    return
for x,y,z in xyz:
    merge(x-1,y-1)
print(par.count(-1))

Submission status: Accepted

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


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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)

for i in range(M):
    X, Y, Z = map(int, input().split())
    X, Y = X - 1, Y - 1
    UF.union(X, Y)
UF.all_find()

print(len(set(UF.par)))

Submission status: Accepted

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


parent = [i for i in range(N)]
rank = [0] * N


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


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

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


for i in range(M):
    X, Y, Z = map(int, input().split())
    X, Y = X - 1, Y - 1
    if not same(X, Y):
        unite(X, Y)

num = 0
for i in range(N):
    if i == find(i):
        num += 1

print(num)

Submission status: Accepted

Solution code:
import scipy.sparse as sp
import scipy.sparse.csgraph as gp


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

adj = sp.dok_matrix((N,N), dtype=bool)
def it():
    for m in range(M):
        x,y,z = map(int,input().split())
        x,y = x-1,y-1
        adj[x,y] = True
        adj[y,x] = True
it()

res,_ = gp.connected_components(adj, directed=False)
print(res)

Submission status: Accepted

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

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

UF = UnionFind(N)
for i in range(M):
  x = hint[i][0]
  y = hint[i][1]
  UF.unite(x, y)
print(len([r for r in UF.root if r < 0]) - 1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]


N, M = list(map(int, input().split()))
X, Y, Z = zip(*[list(map(int, input().split())) for _ in range(M)])

uf = UnionFind(size=(N + 1) * 2)
for x, y, z in zip(X, Y, Z):
    uf.unite(x, y)

roots = set()
ans = 0
for i in range(1, N + 1):
    root = uf.find(i)
    if root not in roots:
        roots.add(root)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.size = n
        self.data = [-1 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def __len__(self):
        return self.size

    def root(self, i):
        """0 <= i < n"""
        if self.data[i] < 0:
            return i
        self.data[i] = self.root(self.data[i])
        return self.data[i]

    def connected(self, i, j):
        return self.root(i) == self.root(j)

    def groupsize(self, i):
        return self.sizes[self.root(i)]

    def roots(self):
        """O(n)"""
        return [i for i, v in enumerate(self.data) if v < 0]

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if (-self.data[i]) < (-self.data[j]):
            self.data[i] = j
            self.sizes[j] += self.sizes[i]
        elif (-self.data[i]) > (-self.data[j]):
            self.data[j] = i
            self.sizes[i] += self.sizes[j]
        else:
            self.data[i] += -1
            self.data[j] = i
            self.sizes[i] += self.sizes[j]


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

print(len(uf.roots()))

Submission status: Accepted

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

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1

N,M=map(int,input().split())        
uf=Unionfind(N)        
for i in range(M):
  x,y,w=map(int,input().split())
  uf.unite(x-1,y-1)
used=[False]*N
ans=0
for i in range(N):
  uf.find(i)
  if not used[uf.Tree[i]]:
    ans+=1
  used[uf.Tree[i]]=True
  
print(ans)
#print(uf.Tree)

Submission status: Accepted

Solution code:
# union-findかな
# 蟻本によればunion-findは分割できないっぽいので、ちょっと違う? 
# 時刻を巻き戻して、橋なしから橋を建設することにすれば扱える

# 橋が崩落してA+B　がAとBに分かれたら、不便度はA*B増加する

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

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

def unite(x, y):
	x = find_root(x)
	y = find_root(y)
	if(x == y):
		return 0

	if rank[x] < rank[y]:
		par[x] = y

		temp = size[x] * size[y]
		size[y] = size[x] + size[y]
	else:
		par[y] = x
		if (rank[x] == rank[y]):
			rank[x] += 11

		temp = size[x] * size[y]
		size[x] = size[x] + size[y]
	return temp

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

# par = [0]*n
par = list(range(n))
rank = [0]*n
size = [1]*n

edges = [list(map(int, input().split()))[0:2] for _ in range(m)]
edges = [[b[0]-1, b[1]-1] for b in edges] #1-idx -> 0-idx

for b in range(m):
	unite(edges[b][0] , edges[b][1])

# print(par)
# print(len(set(par)))

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

print(len(set(arr)))

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()

class UnionFind(object):
    """UnionFind (経路圧縮、ランクあり)"""
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def union(self, n1, n2):
        r1 = self.root(n1)
        r2 = self.root(n2)
        if r1 != r2:
            if self.rank[r1] < self.rank[r2]:
                self.parent[r1] = r2
            else:
                self.parent[r2] = r1
                if self.rank[r1] == self.rank[r2]:
                    self.rank[r1] += 1

    def root(self, node):
        p = self.parent[node]
        if p == node:
            return p
        p = self.root(p)
        self.parent[node] = p
        return p

    def same(self, n1, n2):
        return self.root(n1) == self.root(n2)


def main():
    N, M = MI()
    uf = UnionFind(N)

    for i in range(M):
        x, y, _ = MI()
        uf.union(x-1, y-1)

    return len(set([uf.root(i) for i in range(N)]))


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def find(self, x: int)->int:
        if self.__root[x] < 0:
            return x
        self.__root[x] = self.find(self.__root[x])
        return self.__root[x]

    def union(self, x: int, y: int)->int:
        rx, ry = self.find(x), self.find(y)

        if rx == ry:
            return

        if self.__root[ry] < self.__root[rx]:
            rx, ry = ry, rx

        self.__root[rx] += self.__root[ry]
        self.__root[ry] = rx

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


def one_or_two(N: int, M: int, queries: list)->int:
    uf = UnionFind(N)

    for x, y, _ in queries:
        uf.union(x-1, y-1)

    return len(set(uf.find(i) for i in range(N)))


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]

    ans = one_or_two(N, M, queries)
    print(ans)

Submission status: Accepted

Solution code:
# Union Find # 分割はできない
##############
import sys
sys.setrecursionlimit(int(1e9))

class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: #多い方に合流させる
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)
  
  
N , M = list(map(int, input().split()))
XYZ = [list(map(int, input().split())) for _ in range(M)]

uf = UnionFind()

_set = set()

for x,y,z in XYZ:
  uf.unite(x,y)
  _set.add(x)
  _set.add(y)
  
answer = len(set([uf.find_root(i) for i in _set])) + N-len(_set)
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(114514)

from collections import Counter

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

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

def find(x):
	if g[x] == x:
		return x
	g[x] = find(g[x])
	return g[x]

def union(x, y):
	x = find(x)
	y = find(y)
	if x != y:
		g[x] = y

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

print(len(Counter([find(i) for i in range(1, N+1)])))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class UnionFind:
    def __init__(self, node: int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]

    def find(self, x: int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> bool:
        if self.isSame(x, y):
            # print("x and y has already united")
            return False

        rx = self.find(x)
        ry = self.find(y)

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]

            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

        return True

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


n,m = li()
uf = UnionFind(n)
for _ in range(m):
    x,y,z = li()
    x -= 1
    y -= 1
    uf.unite(x,y)

pars = set()
for i in range(n):
    uf.find(i)
    pars.add(uf.par[i])

print(len(pars))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.data=[-1 for i in range(n)]

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

    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.data[y]<self.data[x]:
            x,y=y,x
        self.data[x]+= self.data[y]
        self.data[y] = x

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

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

n,m=map(int,input().split())
uf=UnionFind(n)
for i in range(m):
    x,y,z=map(int,input().split())
    uf.uni(x-1,y-1)
count=0
for i in range(n):
    if uf.data[i]<0:
        count+=1
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*10**5)


N, M = map(int, input().split())
X, Y, Z = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)

G = [set() for _ in range(N + 1)]
for x, y in zip(X, Y):
    G[x].add(y)
    G[y].add(x)


dp = [-1 for _ in range(N + 1)]


def f(i, k):
    for t in G[i]:
        if dp[t] == -1:
            dp[t] = k
            f(t, k)


L = 0
for i in range(1, N + 1):
    if dp[i] == -1:
        L += 1
        f(i, L)
ans = L
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def par(i):
    if X[i] == i:
        return i
    tmp = par(X[i])
    X[i] = tmp
    return tmp
    
ans = N
for _ in range(M):
    x, y, z = map(int, input().split())
    
    px = par(x-1)
    py = par(y-1)
    if px != py:
        ans -= 1
        X[py] = px

print(ans)

Submission status: Accepted

Solution code:
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):
#    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,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[y] = bx
    A[by] = bx

N, M = map( int, input().split())
V = [ i for i in range(N)]
for _ in range(M):
    x, y,_ = map( int, input().split())
    union(V, x-1, y-1)
print( sum( [1 for i in range(N) if i == V[i]]))

Submission status: Accepted

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

class UnionFind:
    def __init__(self,n):
        self.par=[i for i 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 x==y:
            return
        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 same_check(self,x,y):
        return self.find(x)==self.find(y)

uf=UnionFind(n)
for _ in range(m):
    x,y,z=map(int,input().split())
    x-=1; y-=1
    uf.union(x,y)
Ans=[0]*n
for i in range(n):
    Ans[uf.find(i)]=1
print(sum(Ans))

Submission status: Accepted

Solution code:
class UnionFindTree():
    def __init__(self, N):
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(len(self.__parent_of)):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    uft = UnionFindTree(N)
    for _ in range(M):
        x, y, z = map(int, input().split())
        uft.unite(x-1, y-1)
    print(len(uft.groups()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


class UnionFind(object):
    def __init__(self, N):
        self._parent = list(range(N))
        self.__num_components = [1] * N

    def root(self, x):
        if self._parent[x] == x:
            return x
        else:
            # root abbreviation
            self._parent[x] = self.root(self._parent[x])
            return self._parent[x]

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

    def num_connected(self, x):
        return self.__num_components[self.root(x)]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        rank_x = self.__num_components[x]
        rank_y = self.__num_components[y]
        if rank_x < rank_y:
            self._parent[x] = y
            self.__num_components[y] += rank_x
        else:
            self._parent[y] = x
            self.__num_components[x] += rank_y
        return


fin = sys.stdin.readline
N, M = [int(elem) for elem in fin().split()]
conditions = [tuple(int(elem) - 1 for elem in fin().split()) for _ in range(M)]
uf = UnionFind(N)
for X, Y, _ in conditions:
    uf.unite(X, Y)

num_distinct_components = 0
for i in range(N):
    if uf.root(i) == i:
        num_distinct_components += 1
print(num_distinct_components)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
src = [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.rank = [0] * 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.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

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

Submission status: Accepted

Solution code:
from collections import deque


'''UnionFindクラス'''
class UnionFind:

    def __init__(self, n):
        self.parent =  [-1 for _ in range(n)]

    def root(self, x):
        '''根を返す'''
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        '''xとyの根を結合する'''
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        return

    def is_same(self, x, y):
        '''xとyの根が同じかどうかを返す（根が同じ:True、根が異なる:False）'''
        return self.root(x) == self.root(y)

    def get_size(self, x):
        '''xが含まれる木の要素数を返す'''
        return -self.parent[self.root(x)]


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

graph = [[] for i in range(n)]
for i in range(m):
    graph[info[i][0] - 1].append([info[i][1] - 1, info[i][2]])
    graph[info[i][1] - 1].append([info[i][0] - 1, info[i][2]])

uf = UnionFind(n)
visited = [False]*n
ans = 0
for i in range(n):
    if not visited[i]:
        ans += 1
        visited[i] = True
        q = deque()
        q.append(i)
        while q:
            pos = q.pop()
            for j, cost in graph[pos]:
                if not visited[j]:
                    visited[j] = True
                    q.append(j)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
fa = {i: i for i in range(1, n + 1)}
cnt = n

def getfa(x):
	if fa[x] == x:
		return x
	fa[x] = getfa(fa[x])
	return fa[x]

for i in range(m):
	x, y, z = map(int, input().split())
	fx = getfa(x)
	fy = getfa(y)
	if fx != fy:
		cnt -= 1
	fa[fy] = fx

print(cnt)