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:
from collections import defaultdict, deque

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

d = [0]*(n+1)  # カードの整数が判明したら1にする
ddict = defaultdict(list)  # リスト内のカードと関係がある
relation = [[i, 0] for i in range(1, n+1)]  # iはk枚のカードと関係がある
for _ in range(m):
    x, y, z = map(int, input().split())
    ddict[x].append(y)
    ddict[y].append(x)
    relation[x-1][1] += 1
    relation[y-1][1] += 1
    
relation.sort(reverse=True, key=lambda x: x[1])

ans = 0
for i, r in relation:
    
    if r >=1:  # 他のカードと関係がある
        if d[i] == 0:  # カードの整数は判明していない
            ans += 1
            d[i] = 1
            que = deque(ddict[i])  # 関係のあるカードの整数が判明
            while que:
                s = que.popleft()
                if d[s] == 0:
                    d[s] = 1
                    que += ddict[s]                    
                else:  # 魔法を使う前に判明済み
                    continue
        else:  #カードの整数は判明済み
            continue
            
    else:  # 他のカードと関係がない
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
remains = set(range(1,n+1))
edges = [[] for _ in range(n+1) ]

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

ans = 0
while(len(remains) > 0):
    ans += 1

    d = deque()
    d.append(remains.pop())
    while(len(d) > 0):
        tmp = d.pop()
        for i in edges[tmp]:
            if( i in remains):
                d.append(i)
                remains.remove(i)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc126/tasks/abc126_e

# 偶奇を当てる問題
# 制約 A_Xi + A_Yi + Zi は偶数

# もしZiが偶数のとき
# A_Xi , A_Yiは偶,偶 or 奇,奇

# もしZiが奇数なら
# A_Xi , A_Yiは偶,奇 or 奇,偶

# A_XiとA_Yiについて符号が違うか同じかをメモしておけば良い？
# 未確定なAiについて魔法を使う必要がある

# Aiのiをノードとして捉えたとき、ノードXj, Yjは'同じまとまり'としてマージし続けられる
# 同じまとまりに対しては一つのAiを確定させれば、そのまとまりすべてのAiが判明する。
# よってdisjointになっている集合の数が答えになる。


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)

    def n_disjoint(self):
        # O(N)かかる
        return sum([x < 0 for x in self.parent])


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
uf = UnionFind(N)
for m in range(M):
    x, y, z = read_ints()
    uf.unite(x - 1, y - 1)

print(uf.n_disjoint())

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, 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


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

print(sum([x < 0 for x in uf.parents]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
  x, y, z = map(int, input().split())
  adj[x-1].append(y-1)
  adj[y-1].append(x-1)
opn = [True] * n
count = 0
for i in range(n):
  if opn[i]:
    count += 1
    opn[i] = False
    stack = [i]
    while stack:
      u = stack.pop()
      for v in adj[u]:
        if opn[v]:
          stack.append(v)
          opn[v] = False
print(count)

Submission status: Accepted

Solution code:
class union_find():
  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 main():
  N,M=map(int,input().split())
  box=union_find(N)
  for i in range(M):
    x,y,z=map(int,input().split())
    box.union(x-1,y-1)
  box.find(1)
  ans=0
  for i, x in enumerate(box.parents):
    if x<0:
      ans+=1
  print(ans)
main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
#union-find
par=[-1]*(n+1)
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def size(x):
    oya=find(x)
    return -par[oya]
def unite(x,y):
    if find(x)==find(y):
        return False
    else:
        if size(y)>size(x):
            y,x=x,y  #xを大きい親にしておくか
        oya_x=find(x)
        oya_y=find(y)
        par[oya_x]-=size(oya_y)  #xの大きさをyにしておく
        par[oya_y]=oya_x  #yの親をxに
        return True

def is_same(x,y):
    return find(x)==find(y)
for _ in range(m):
    x,y,z=map(int,input().split())
    unite(x,y)
ans_set=set()
for i in range(1,n+1):
    ans_set.add(find(i))
print(len(ans_set))

Submission status: Accepted

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

class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(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 unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

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

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

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

ans = set()
for i in range(N):
  ans.add(uf.root(i))
print(len(ans))

Submission status: Accepted

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)


class UnionFind:
    def __init__(self, size):
        # -nが木のroot
        #親ノードの位置を格納
        self.table = [-1 for i in range(size)]

    def _find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def find(self, x):
        if self.table[x] < 0:
            return x
        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 get_ntree(self):
        res = 0
        for c in self.table:
            if c < 0:
                res += 1
        return res

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

    def get_nclass(self):
        done = []
        for x in range(len(self.table)):
            if x in done:
                continue
            while self.table[x] >= 0:
                done.append(x)
                x = self.table[x]

    def get_nodenum(self):
        res = []
        for t in self.table:
            if t < 0:
                res.append(-t)

        return res



def acinput():
    return list(map(int, input().split(" ")))



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count


N,M=acinput()

uf = UnionFind(N)

for i in range(M):
    tmp = acinput()
    uf.union(tmp[0]-1,tmp[1]-1)


print(uf.get_ntree())

Submission status: Accepted

Solution code:
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y, z = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

def main():
    to_check = set(range(1, n+1))
    checked = set()
    cnt = 0
    while to_check:
        queue = set([to_check.pop()])
        cnt += 1
        while queue:
            v = queue.pop()
            checked.add(v)
            to_check -= set([v])
            for u in graph[v]:
                if not u in checked:
                    queue.add(u)
    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

n, m, *xyz = map(int, sys.stdin.read().split())
xyz = zip(*[iter(xyz)] * 3)

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

sys.setrecursionlimit(10**7)
def find_root(v):
    u = root[v]
    if u == v:
        return u
    w = find_root(u)
    root[v] = w
    return w

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

def main():
    for x, y, z in xyz:
        unite(x, y)
    
    for i in range(1, n+1):
        find_root(i)

    return len(set(root[1:]))

if __name__ == '__main__':
    ans = main()
    print(ans)

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:
class UnionFind():
    def __init__(self, N):
        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]:
                self.rank[x] += 1
            elif self.rank[x] < self.rank[y]:
                x, y = y, x
            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())
    x, y = x-1, y-1
    uf.union(x, y)

s = set()
for i in range(n):
    parent = uf.find(i)
    s.add(parent)
print(len(s))

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

N, M = map(int, input().split())
edge = np.array([input().split() for _ in range(M)], dtype=np.int64).T

matr = csr_matrix(([1 for _ in range(M)], (edge[:2] - 1)), (N, N))
print(connected_components(matr, return_labels=False))

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import deque
n,m=map(int,input().split())
d=dict()
edge=[[] for i in range(n)]
for i in range(m):
  x,y,z=map(int,input().split())
  edge[x-1].append(y-1)
  edge[y-1].append(x-1)
  if x-1 not in d:
    d[x-1]=1
  else:
    d[x-1]+=1
  if y-1 not in d:
    d[y-1]=1
  else:
    d[y-1]+=1
d=sorted(list(d.items()),key=itemgetter(1),reverse=True)
visited=[0]*n
def bfs(edge,visited,s):
  q=deque([s])
  visited[s]=1
  while q:
    x=q.popleft()
    for i in edge[x]:
      newx=i
      if newx<n:
        if visited[newx]!=1:
          visited[newx]=1
          q.append(newx)
  return visited
ans=0
for i in range(len(d)):
  if visited[d[i][0]]==0:
    visited=bfs(edge,visited,d[i][0])
    ans+=1
print(ans+n-sum(visited))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**5)

def main():
    N,M = map(int,input().split())
    use = [False for _ in range(N)]
    formula = 0
    
    I = [i for i in range(N)]
    rank = [1 for _ in range(N)]
    def root(x):
        if x == I[x]:
            return x
        I[x] = root(I[x])
        return I[x]
    
    def unite(x,y):
        px,py = root(x),root(y)
        rx,ry = rank[px],rank[py]
        if rx > ry:
            I[py] = px
        else:
            I[px] = py
            if rx == ry:
                rank[py] += 1

    for i in range(M):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        px,py = root(x),root(y)
        if px == py:
            continue
        else:
            unite(x,y)
            formula += 1

    print(N-formula)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**5)

def main():
    N,M = map(int,input().split())
    use = [False for _ in range(N)]
    formula = 0
    
    I = [i for i in range(N)]
    rank = [1 for _ in range(N)]
    def root(x):
        if x == I[x]:
            return x
        I[x] = root(I[x])
        return I[x]
    
    def unite(x,y):
        px,py = root(x),root(y)
        if x < y:
            I[py] = px
        else:
            I[px] = py

    for i in range(M):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        px,py = root(x),root(y)
        if px == py:
            continue
        else:
            unite(x,y)
            formula += 1

    print(N-formula)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
edge = {i: [] for i in range(1, n+1)}
graph = {i: -1 for i in range(1, n+1)}

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

def color_graph(i, v):
  if graph[i] == -1:
    graph[i] = v
    for j in edge[i]:
      color_graph(j, v)

ans = 0
for i in range(1, n+1):
  if graph[i] == -1:
    ans += 1
    color_graph(i, i)


print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n  # 根のノードは限らないので注意

    def find(self, x):  # あるノードの親を探すためのメソッド
        if self.parents[x] < 0:  # 親の場合、要素の個数を負の値で保持している
            return x  # 自身が親であるということ
        else:
            self.parents[x] = self.find(self.parents[x])  # 再帰的に親を探しにいく
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)  # この変数xに格納されているものは必ず根のノード
        y = self.find(y)  # この変数yに格納されているものは必ず根のノード
        if x == y:
            return  # もし同じ親ならば何も起こらない

        if self.parents[x] > self.parents[y]:  # それぞれ、要素の個数が負で格納されている
            # yのグループの方が要素が多いの場合（yの方が値が小さいということは、負の世界では値が大きいため）
            x, y = y, x  # 必ずxの方が要素が多い状態にする

        self.parents[x] += self.parents[y]  # 負の値だが、これでいい
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    def size(self, x):
        return -self.parents[self.find(x)]  # 親まで辿ればグループの大きさが負で格納されているため、それにマイナスをつけてreturnする

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 親が同じならTrueが返却される

    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_counts(self):
        return len(self.roots())  # グループの数を返す

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}  # 親のノード番号をキーにして、子のノードを対応させた辞書を返す

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


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

print(uf.group_counts())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

class UnionFind:
    def __init__(self, n):
        # par = Parent Number or NoV
        self.par = [-1] * (n+1)
        # rank = Tree Height
        self.rank = [0] * (n+1)
    
    # 自分が所属する集合の数を返す
    def size(self, x):
        return -1*self.par[self.find(x)]
    
    def size_list(self):
        return [x*(-1) for x in self.par[1:] if x < 0]

    # 根なら番号を返す
    def find(self, x):
        
        if(self.par[x] < 1):
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    # 親が同じか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # もう繋がれている
        if(x == y):
            return False

        # つなぎ替える
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        # xのサイズを更新
        self.par[x] += self.par[y]
        # yのサイズ(おやばんごう)をxに
        self.par[y] = x

        return True 

    def root_nodes(self):
        # print([i for i in self.par[1:]])
        return len([i for i in self.par[1:] if i <= -1])


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.union(X[i], Y[i])
    print(uf.root_nodes())
    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:
N,M = map(int,input().split())
xy = [[] for i in range(N)]
alr = [1 for i in range(N)]
for i in range(M):
    x,y,z = map(int,input().split())
    xy[x-1].append(y-1)
    xy[y-1].append(x-1)
    alr[x-1] = 0
    alr[y-1] = 0
count = sum(alr)
stack = []
for i in range(N):
    if not alr[i]:
        stack.append(xy[i])
        alr[i] = 1
        if xy[i]:
            count += 1
        while stack:
            now = stack.pop()
            for j in now:
                if not alr[j]:
                    alr[j] = 1
                    stack.append(xy[j])
print(count)

Submission status: Accepted

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
N = gi()
M = gi()
parent = [[] for i in range(N + 1)]


def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])

    return parent[a]


def union(a, b):
    aP = find(a)
    bP = find(b)

    if (aP != bP):
        parent[max(aP, bP)] = min(aP, bP)


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

for i in range(M):
    x = gi()
    y = gi()
    z = gi()
    union(x, y)

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

def visit_tree(now, num):
    visited[now] = num
    for i in range(len(tree[now])):
        if not visited[tree[now][i]]:
            visit_tree(tree[now][i], num)

n, m = map(int, input().split())
tree = [[] for _ 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)

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)

Submission status: Accepted

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

#情報のつながりがあるカードでグルーピングする
#グループIDのリスト(0は未割り当て)
G=[0]*(N+1)

def dfs(root,g):
    stack=[root]
    G[root]=g
    while stack:
        node=stack.pop()
        for to in E[node]:
            if G[to]==0:
                G[to]=g
                stack.append(to)

ans=0
for i in range(N):
    if G[i]==0:
        ans+=1
        dfs(i,ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)


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

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

def dfs(now):
    SEARCHED[now] = True
    for v in GRAPH[now]:
        if SEARCHED[v]:
            continue
        next = v
        dfs(next)

SEARCHED = {i:False for i in range(1, n + 1)}
count = 0
for i in range(1, n + 1):
    if SEARCHED[i]:
        continue
    dfs(i)
    count += 1

print(count)

Submission status: Accepted

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

e_list = [[] for i in range(N)]

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

count = 0

color_list = [-1]*N

from collections import deque

def BFS(vi,c):
    Q = deque([vi])
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color_list[v1]==-1:
                color_list[v1]=c
                Q.appendleft(v1)

for i in range(N):
    if color_list[i]==-1:
        BFS(i,count)
        count+=1

print(count)

Submission status: Accepted

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
N, M = list(map(int, input().split()))
uf = UnionFind(N)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    global gone
    stack = [v]
    gone[v] = True
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if gone[w] == False:
                stack.append(w)
            gone[w] = True

n,m = map(int,input().split())
exist = [False for i in range(n+1)]
gone = [False for i in range(n+1)]
graph = [[] for _ in range(n+1)]
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
    exist[x] = True
    exist[y] = True
ans = 0

for i in range(1,n+1):
    if exist[i] == True:
        if gone[i] == False:
            dfs(i)
            ans += 1
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

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

    def union(self, id1, id2):
        par1, par2 = self.find(id1), self.find(id2)
        if par1 == par2:
            return
        if self.rank[par1] > self.rank[par2]:
            self.parent[par2] = par1
        else:
            self.parent[par1] = par2
            if self.rank[par1] == self.rank[par2]:
                self.rank[par2] += 1
        self.size -= 1

nVertices, nEdges = map(int, input().split())
unionFind = UnionFind(nVertices)
for _ in range(nEdges):
    u, v, _ = map(lambda x: int(x) - 1, input().split())
    unionFind.union(u, v)
print(unionFind.size)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)
from collections import deque

nVertices, nEdges = map(int, input().split())
g = [[] for _ in range(nVertices + 1)]
for _ in range(nEdges):
    u, v, _ = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

def dfs(v):
    visited[v] = True
    for to in g[v]:
        if not visited[to]:
            dfs(to)

def bfs(v):
    visited[v] = True
    q = deque([v])
    while q:
        cur = q.pop()
        for to in g[cur]:
            if not visited[to]:
                visited[to] = True
                q.appendleft(to)

cnt = 0
visited = [False] * (nVertices + 1)
for v in range(1, nVertices + 1):
    if not visited[v]:
        bfs(v)
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    edges[x - 1].append(y - 1)
    edges[y - 1].append(x - 1)
visited = [False] * n
ret = 0
for i in range(n):
    if not visited[i]:
        q = [i]
        visited[i] = True
        while len(q) > 0:
            u = q.pop(0)
            for v in edges[u]:
                if not visited[v]:
                    q.append(v)
                    visited[v] = True
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import time
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)

class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

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

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

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

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

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)




def solve():
    return

#入力
N,M=map(int,input().split())
XYZ=[]

U=union_find(N)
for a in range(M):
    X,Y,Z=map(int,input().split())
    X-=1
    Y-=1
    U.unite(X,Y)
print(U.size())

Submission status: Accepted

Solution code:

from collections import defaultdict
import heapq

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

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


q = []

for k in counts.keys():
    heapq.heappush(q, (-counts[k], k))

visited = [False] * N
stack = []
cnt = 0
while q:
    _, curr = heapq.heappop(q)
    if visited[curr]:
        continue
    cnt += 1
    stack.append(curr)
    while stack:
        ns = stack.pop()
        if visited[ns]:
            continue
        visited[ns] = True
        for nns in es[ns]:
            if not visited[nns]:
                stack.append(nns)

print(visited.count(False) + cnt)