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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
# from collections import deque, Counter                          # キュー・個数カウント
# from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
# from operator    import itemgetter                              # ソート補助
# from bisect      import bisect_left, bisect_right, bisect       # 二分探索
# from heapq       import heappop, heappush                       # プライオリティキュー
# from fractions   import gcd                                     # 最大公約数
# from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
# from copy        import deepcopy                                # オブジェクトコピー
# import numpy         as np                                      # 数値計算

input = sys.stdin.readline

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n, m = im.inputMultiple()
    A = [Node(i) for i in range(n)]
    appearList = [False for i in range(n)]
    for i in range(m):
        x, y, z = im.inputMultiple()
        appearList[x-1] = True
        appearList[y-1] = True
        A[x-1].addConnection(A[y-1])
        A[y-1].addConnection(A[x-1])
    # Logic ############################################################################################################
    count = 0
    knownList = [False for i in range(n)]
    for i, appeared in enumerate(appearList):
        if appeared == False:
            knownList[i] = True
            count += 1
    while (False in knownList):
        idx = knownList.index(False)
        Node.checkKnown(A[idx], knownList)
        count += 1
    # Output ###########################################################################################################
    print(count)
    # Return ###########################################################################################################
    return

class Node:
    def __init__(self, index):
        self._index = index
        self._connections = []
    
    @property
    def index(self):
        return self._index
    
    @property
    def connections(self):
        return self._connections
    
    def addConnection(self, node):
        self._connections.append(node)
    
    @staticmethod
    def checkKnown(node, knownList):
        if knownList[node.index] == False:
            knownList[node.index] = True
            for connectioon in node.connections:
                Node.checkKnown(connectioon, knownList)
        else:
            return

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

input = sys.stdin.readline

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n, m = im.inputMultiple()
    A = [Node(i) for i in range(n)]
    appearList = [False for i in range(n)]
    for i in range(m):
        x, y, z = im.inputMultiple()
        appearList[x-1] = True
        appearList[y-1] = True
        A[x-1].addConnection(A[y-1])
        A[y-1].addConnection(A[x-1])
    # Logic ############################################################################################################
    count = 0
    knownList = [False for i in range(n)]
    for i, appeared in enumerate(appearList):
        if appeared == False:
            knownList[i] = True
            count += 1
    while (False in knownList):
        idx = knownList.index(False)
        Node.checkKnown(A[idx], knownList)
        count += 1
    # Output ###########################################################################################################
    print(count)
    # Return ###########################################################################################################
    return

class Node:
    def __init__(self, index):
        self._index = index
        self._connections = []
    
    @property
    def index(self):
        return self._index
    
    @property
    def connections(self):
        return self._connections
    
    def addConnection(self, node):
        self._connections.append(node)
    
    @staticmethod
    def checkKnown(node, knownList):
        if knownList[node.index] == False:
            knownList[node.index] = True
            for connectioon in node.connections:
                Node.checkKnown(connectioon, knownList)
        else:
            return

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
count = 0
groups = 0
label=np.zeros((100000),int)
for i in range(0, M):
  a, b, c = map(int, input().split())
  a=a-1
  b=b-1
  if label[a]==0 and label[b]==0:
    count=count+1
    groups=groups+1
    label[a]=groups
    label[b]=groups
  elif label[a]==0 and label[b]!=0:
    count=count+1
    label[a]=label[b]
  elif label[a]!=0 and label[b]==0:
    count=count+1
    label[b]=label[a]
  elif label[a]!=label[b]:
    count=count+1
    tp=label[b]
    label=np.where(label==tp,label[a],label)
print(N-count);

Submission status: Time Limit Exceeded

Solution code:
'''input
100000 1
1 100000 100
'''
import sys
sys.setrecursionlimit(100100)
N, M = [int(x) for x in input().split()]

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

for _ in range(M):
	a, b, w = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	w = w & 1
	vien[a].append(b)
	vien[b].append(a)

been = [False]*N
ats = 0
def dfs(x):
	been[x] = True
	for u in vien[x]:
		if not been[u]:
			dfs(u)


for i in range(N):
	if been[i]: continue

	ats += 1
	dfs(i)

print(ats)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 6)

def dfs(n):
    # print('Search Start: ' + str(n))
    if checked[n]:
        # print('Checked: ' + str(n))
        return
    checked[n] = True
    for e in edge:
        if n in e:
            x, y = e
            if n != x:
                dfs(x)
            else:
                dfs(y)
    # print('Search End: ' + str(n))

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

edge = [] * M
checked = [False for _ in range(N)]

con_com = 0

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

for i in range(N):
    if checked[i]:
        continue
    dfs(i)
    # print('--- Connected Components ---')
    con_com += 1

print(con_com)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n, m = im.inputMultiple()
    A = [Node(i) for i in range(n)]
    appearList = [False for i in range(n)]
    for i in range(m):
        x, y, z = im.inputMultiple()
        appearList[x-1] = True
        appearList[y-1] = True
        A[x-1].addConnection(A[y-1])
        A[y-1].addConnection(A[x-1])
    # Logic ############################################################################################################
    count = 0
    knownList = [False for i in range(n)]
    for i, appeared in enumerate(appearList):
        if appeared == False:
            knownList[i] = True
            count += 1
    while (False in knownList):
        idx = knownList.index(False)
        Node.checkKnown(A[idx], knownList)
        count += 1
    # Output ###########################################################################################################
    print(count)
    # Return ###########################################################################################################
    return

class Node:
    def __init__(self, index):
        self._index = index
        self._connections = []
    
    @property
    def index(self):
        return self._index
    
    @property
    def connections(self):
        return self._connections
    
    def addConnection(self, node):
        self._connections.append(node)
    
    @staticmethod
    def checkKnown(node, knownList):
        if knownList[node.index] == False:
            knownList[node.index] = True
            for connectioon in node.connections:
                Node.checkKnown(connectioon, knownList)
        else:
            return

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Time Limit Exceeded

Solution code:
N,M = input().split()
N = int(N)
M = int(M)
list = []
A_list = []

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

A_list.append([list[0][0]])
for data in list:
    check = 0
    for A_data in A_list:
        if data[0] in A_data:
            A_data.append(data[1])
            check = 0
        elif data[1] in A_data:
            A_data.append(data[0])
            check = 0
        elif not data[0] in A_data and not data[1] in A_data:
            check = 1
    if check:
        A_list.append([data[0],data[1]])

x = []
for s in A_list:
    x.extend(s)

x = len(set(x))
count = len(A_list)

ans = N - x + count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def readInts():
  return [int(s) for s in input().split(" ")]

def root(groups, n):
  while groups[n] != n:
    n = groups[n]
  return n

def union(groups, x, y):
  rx = root(groups, x)
  ry = root(groups, y)
  if rx != ry:
    groups[ry] = rx

def main():
  N, M = readInts()
  groups = [i for i in range(N)]

  for i in range(M):
    X, Y, Z = readInts()
    union(groups, X-1, Y-1)

  knowns = set()
  for n in range(N):
    knowns.add(root(groups, n))
  print(len(knowns))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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



graph_indexes=[i for i in range(N)] #それぞれの数は, どのグラフに含まれているのか
graphs=[[i] for i in range(N)] #実際のグラフ

for i in range(M):
	X,Y,Z=[int(c)-1 for c in input().split()]
	X_i=graph_indexes[X]
	Y_i=graph_indexes[Y]
	if(X_i!=Y_i):
		graphs[X_i].extend(graphs[Y_i])
		for j in graphs[Y_i]:
			graph_indexes[j]=graph_indexes[X]

		graphs[Y_i]=[]
		#graph_indexes[Y]=graph_indexes[X]
		#[0,1,2,3][4,5,6]
		#gi[3]=0

		#[0,1,2,3,4,5,6]
	

i=0
for g in graphs:
	if(g!=[]):
		i+=1
print(i)

Submission status: Time Limit Exceeded

Solution code:
N,M = input().split()
N = int(N)
M = int(M)
list = []
A_list = []

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

A_list.append([list[0][0]])
for data in list:
    check = 0
    for A_data in A_list:
        if data[0] in A_data:
            A_data.append(data[1])
            check = 0
        elif data[1] in A_data:
            A_data.append(data[0])
            check = 0
        elif not data[0] in A_data and not data[1] in A_data:
            check = 1
    if check:
        A_list.append([data[0],data[1]])

x = []
for s in A_list:
    x.extend(s)
count = len(A_list)
for i in range(N):
    if not i+1 in x:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(n):
    # print('Search Start: ' + str(n))
    # print(graph)
    stack1 = graph[n]
    while stack1:
        x = stack1.popleft()
        dfs(x)
    for i in range(N):
        if n in graph[i]:
            dfs(i)
    checked[n] = True
    # print('Search End: ' + str(n))

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

graph = {i: deque() for i in range(N)}
checked = [False for _ in range(N)]

con_com = 0

for _ in range(M):
    x, y, _ = list(map(int, input().split()))
    graph[min(x, y)-1].append(max(x, y)-1)

for i in range(N):
    if checked[i]:
        continue
    dfs(i)
    # print('--- Connected Components ---')
    con_com += 1

print(con_com)

Submission status: Time Limit Exceeded

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

checked = [x for x in range(1,n+1)] #checked = 0
xyz.sort()
ans=n
for i in xyz:
    x,y,z = i
    if x in checked and y in checked:
        checked[x-1]=0
        checked[y-1]=0
        ans-=1 #no check
    elif x in checked or y in checked:
        checked[x-1]=0
        checked[y-1]=0
        ans-=1 #one check
    else:
        pass
print(ans)

Submission status: Time Limit Exceeded

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

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

sets = list()
for i in range(M):
    x, y, z = list(map(int, input().split()))
    flag = True
    for s in sets:
        if x in s or y in s:
            if not flag:
                s |= _s
                s |= {x, y}
                sets.remove(_s)
                break
            s |= {x, y}
            flag = False
            _s = s
    else:
        if flag:
            sets.append({x, y})


# calc len
num = sum([len(m) - 1 for m in sets])
total = sum([len(m) for m in sets])
print((total-num) + N-total)

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(x) for x in input().split())
l = [[None]*3 for i in range(M)]
for i in range (M):
    index = 0
    for x in input().split():
        l[i][index] = int(x)
        index += 1

X = [l[i][0] for i in range(M)]
Y = [l[i][1] for i in range(M)]
Z = [l[i][2] for i in range(M)]

conn_blocks = [[X[0], Y[0]]]
index_list = list(range(1, N+1))
index_list.remove(X[0])
index_list.remove(Y[0])
for i in range(1, M):
    ind = 0
    for block in conn_blocks:
        if X[i] in block:
            block.append(Y[i])
        elif Y[i] in block:
            block.append(X[i])
        else:
            ind += 1

        if ind == len(conn_blocks):
            conn_blocks.append([X[i], Y[i]])
    if X[i] in index_list:
        index_list.remove(X[i])
    if Y[i] in index_list:
        index_list.remove(Y[i])

print(len(conn_blocks)+len(index_list))

Submission status: Time Limit Exceeded

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

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

for i in range(M):
    X, Y, Z = list(map(int, input().split()))
    for i, el in enumerate(L):
        if X in el:
            X_i = i
            break
    X_L = L.pop(X_i)
    Y_i = -1
    for i, el in enumerate(L):
        if Y in el:
            Y_i = i
            break
    if Y_i != -1:
        Y_L = L.pop(Y_i)
        X_L.extend(Y_L)
    L.append(X_L)
print(len(L))

Submission status: Time Limit Exceeded

Solution code:
n,m=list(map(int,input().split()))
#チェックしたか
checked=[False]*n
#辺があるか（左が小さい）
matrix=[[False]*n for _ in range(n)]
for i in range(m):
  u,v,a=list(map(int,input().split()))
  matrix[u-1][v-1] = True

ans=0

#閉路があればFalse,なければTrue
#既にチェック済のところを踏んだら閉路
def check(c,pre):
  flg=True
  checked[c]=True
  for i in range(n):
    if pre != i and matrix[min(c,i)][max(c,i)]:
      if checked[i]:
        flg=False
  return flg

for i in range(n):
  if checked[i]==False:
    if check(i,-1):
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

N,M=[int(c) for c in input().split()]



graph_indexes=[i for i in range(N)] #それぞれの数は, どのグラフに含まれているのか
graphs=[[i] for i in range(N)] #実際のグラフ

for i in range(M):
	X,Y,Z=[int(c)-1 for c in input().split()]
	X_i=graph_indexes[X]
	Y_i=graph_indexes[Y]
	if(X_i!=Y_i):
		graphs[X_i].extend(graphs[Y_i])
		for j in graphs[Y_i]:
			graph_indexes[j]=graph_indexes[X]

		graphs[Y_i]=[]
		#graph_indexes[Y]=graph_indexes[X]
		#[0,1,2,3][4,5,6]
		#gi[3]=0

		#[0,1,2,3,4,5,6]
	

i=0
for g in graphs:
	if(g!=[]):
		i+=1
print(i)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=[]
for i in range(M):
    A.append([j for j in map(int,input().split())])

sets=[]
i=0
x=A[i][0]
y=A[i][1]
sets.append(set([x,y]))

for i in range(1,M):
    x=A[i][0]
    y=A[i][1]
    count=0
    for k,set1 in enumerate(sets):
        if (x in  set1) or (y in set1):
            if count==0:
                set1.add(x)
                set1.add(y)
                count=k
            else:
                sets[count]=sets[count] | sets[k]
                sets.pop(k)
        else:
            sets.append(set([x,y]))
#print(sets)

all_sets=set()
for set2 in sets:
    all_sets=all_sets|set2

count=N-len(all_sets)

print(len(sets)+count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
n = []
G = []
d = {i: 0 for i in range(1, N+1)}
for i in range(M):
    x, y, z = map(int, input().split())
    n.append([x, y])
    d[x] = 1
    d[y] = 1
for i in n:
    flg = False
    for g in G:
        if i[0] in g:
            g.append(i[1])
            flg = True
            break
        elif i[1] in G:
            g.append(i[0])
            flg = True
            break
    if flg == False:
        G.append([i[0], i[1]])
cnt = 0
for i in range(1, N+1):
    if d[i] == 0:
        cnt += 1
print(cnt + len(G))

Submission status: Time Limit Exceeded

Solution code:
list=input().split(" ")
n=int(list[0])
m=int(list[1])

siki=[]

for i in range(m):
    list=input().split(" ")
    a=int(list[0])
    b=int(list[1])
    siki.append([a,b])

katamari=[]
katamari.append(siki[0])
dekai=siki[0][1]
nanko=1

siki=siki[1:]

for sk in siki:
    aswitch=0
    bswitch=0
    ais=0
    bis=0
    
    f=sk[0]
    g=sk[1]
    h=sk
    
    for kt in katamari:
        if f in kt:
            aswitch=1
        else:
            ais+=1
        if g in kt:
            bswitch=1
        else:
            bis+=1
    if aswitch==0:
        if bswitch==0:
            katamari.append(h)
            nanko+=1
        else:
            katamari[bis].append(f)
            nanko+=1
    else:
        if bswitch==0:
            katamari[ais].append(g)
            nanko+=1
        else:
            if ais!=bis:
                sho=min(ais, bis)
                dai=max(ais, bis)
                katamari[sho]+=katamari[dai]
                if sho+1>=len(katamari):
                    katamari=katamari[:dai]
                    nanko+=1
                else:
                    katamari=katamari[:dai]+katamari[dai+1:]
                    nanko+=1
#print(katamari)
print(n-nanko)

Submission status: Time Limit Exceeded

Solution code:
import sys

array = []
for line in sys.stdin.readlines():
    array.append(line.rstrip().split())
    
n_list = []
cost = 0
for i in range(int(array[0][1])):
    xi = int(array[i+1][0])
    yi = int(array[i+1][1])
    
    if xi not in n_list and yi not in n_list:
        cost += 1
    n_list.append(xi)
    n_list.append(yi)
    
for i in range(int(array[0][0])):
    if i + 1 not in list(set(n_list)):
        cost +=1
        
print(cost)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
X, Y, Z = [0] * M, [0] * M, [0] * M
for i in range(M):
	X[i], Y[i], Z[i] = map(int, input().split())
Groups = [[X[0], Y[0]]]
for i in range(1, M):
	flag = False
	for g in Groups:
		if X[i] in g:
			g.append(Y[i])
			flag = True
		elif Y[i] in g:
			g.append(X[i])
			flag = True
	if flag == False:
		Groups.append([X[i], Y[i]])
cnt = 0
for j in range(1, N + 1):
	flag = False
	for g in Groups:
		if j in g:
			flag = True
	if flag == False:
		cnt += 1
print(len(Groups) + cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

class UnionFind():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self.parent = [n for n in range(0, N)]
        # グループの深さ
        self.size = [1] * N

    def find(self, x):
        """ 木の根(どのグループか)を求める """
        if self.parent[x] == x: return x
        self.parent[x] = self.find(self.parent[x]) # 縮約
        return self.parent[x]

    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self.size[gx] < self.size[gy]:
            self.parent[gx] = gy
            self.size[gy] += self.size[gx]
        else:
            self.parent[gy] = gx
            self.size[gx] += self.size[gy]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find(x) == self.find(y)


def solve():
    N, M = list(map(int, input().split()))
    X, Y, Z = [], [], []
    uf = UnionFind(N)
    for i in range(M):
        x, y, z = list(map(int, input().split()))
        x, y = x-1, y-1
        uf.unite(x, y)
    
    # 答えは、(グループの数) 
    groups = []
    for i in range(N):
        if not uf.find(i) in groups:
            groups.append(uf.find(i))
    
    print(len(groups))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
list=input().split(" ")
n=int(list[0])
m=int(list[1])

siki=[]

for i in range(m):
    list=input().split(" ")
    a=int(list[0])
    b=int(list[1])
    siki.append([a,b])

#print(siki)
#siki.sort(key=itemgetter(1))
#print(siki)

katamari=[]
katamari.append(siki[0])
dekai=siki[0][1]
nanko=1

siki=siki[1:]

for sk in siki:
    aswitch=0
    bswitch=0
    ais=0
    bis=0
    for kt in katamari:
        if sk[0] in kt:
            aswitch=1
        else:
            ais+=1
        if sk[1] in kt:
            bswitch=1
        else:
            bis+=1
    if aswitch==0:
        if bswitch==0:
            katamari.append(sk)
            nanko+=1
        else:
            katamari[bis].append(sk[0])
            nanko+=1
    else:
        if bswitch==0:
            katamari[ais].append(sk[1])
            nanko+=1
        else:
            if ais!=bis:
                sho=min(ais, bis)
                dai=max(ais, bis)
                katamari[sho]+=katamari[dai]
                if sho+1>=len(katamari):
                    katamari=katamari[:dai]
                    nanko+=1
                else:
                    katamari=katamari[:dai]+katamari[dai+1:]
                    nanko+=1
#print(katamari)
print(n-nanko)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=[]
for i in range(M):
    A.append([j for j in map(int,input().split())])

sets=[]
i=0
x=A[i][0]
y=A[i][1]
sets.append(set([x,y]))

for i in range(1,M):
    x=A[i][0]
    y=A[i][1]
    count=0
    for k,set1 in enumerate(sets):
        if (x in  set1) or (y in set1):
            if count==0:
                set1.add(x)
                set1.add(y)
                count=k
            else:
                sets[count]=sets[count] | sets[k]
                sets.pop(k)
        else:
            sets.append(set([x,y]))
#print(sets)

count=0
for j in range(1,N+1):
    for set2 in sets:
        if j in set2:
            count+=1
ans2=N-count
#print(ans2)

print(len(sets)+ans2)

Submission status: Time Limit Exceeded

Solution code:
list=input().split(" ")
n=int(list[0])
m=int(list[1])

siki=[]

for i in range(m):
    list=input().split(" ")
    a=int(list[0])
    b=int(list[1])
    siki.append([a,b])

#print(siki)
#siki.sort(key=itemgetter(1))
#print(siki)

katamari=[]
katamari.append(siki[0])
dekai=siki[0][1]
nanko=1

siki=siki[1:]

for sk in siki:
    aswitch=0
    bswitch=0
    ais=0
    bis=0
    #print(katamari)
    #print(nanko)
    for kt in katamari:
        if sk[0] in kt:
            aswitch=1
            break
        else:
            ais+=1
    for kt in katamari:
        if sk[1] in kt:
            bswitch=1
            break
        else:
            bis+=1
    if aswitch==0:
        if bswitch==0:
            katamari.append(sk)
            nanko+=1
        else:
            katamari[bis].append(sk[0])
            nanko+=1
    else:
        if bswitch==0:
            katamari[ais].append(sk[1])
            nanko+=1
        else:
            if ais!=bis:
                sho=min(ais, bis)
                dai=max(ais, bis)
                for kd in katamari[dai]:
                    katamari[sho].append(kd)
                if sho+1>=len(katamari):
                    katamari=katamari[:dai]
                    nanko+=1
                else:
                    katamari=katamari[:dai]+katamari[dai+1:]
                    nanko+=1
print(n-nanko)

Submission status: Time Limit Exceeded

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

for m in range(M):
    x, y, z = map(int, input().split())
    flag_non_chain = True
    cnt = 0
    for chain in chain_list:
        if x in chain or y in chain:
            chain = chain.union({x, y})
            flag_non_chain = False
        chain_list[cnt] = chain
        cnt += 1
    if flag_non_chain == True:
        chain_list.append({x, y})

num_chain_total = 0

for chain in chain_list:
    num_chain_total += len(chain) - 1

print(N - num_chain_total)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split(" "))
group_list = list()
check = [-1 for i in range(N)]
g_num = 0
for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    if check[x] == -1:
        if check[y] == -1:
            check[x] = g_num
            check[y] = g_num
            g_num += 1
        else:
            check[x] = check[y]
    else:
        if check[y] == -1:
            check[y] = check[x]
        else:
            _from = check[y]
            _to = check[x]
            for i in range(N):
                if check[i] == _from:
                    check[i] == _to

s = set(check)
s.add(-1)
s.remove(-1)
count = 0
for i in range(N):
    if check[i] == -1:
        count += 1
print(count + len(s))