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:
N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
for i in range(1, 10 ** 5 + 1):
    s = visited.index(0)
    stack = [s]
    visited[s] = 1
    while stack:
        st = stack.pop()
        for to in t[st]:
            if visited[to]:
                continue
            visited[to] = 1
            stack.append(to)
    if min(visited):
        ans = i
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
N, M = map(int, input().split())
matrix = np.array([[0] * N for _ in range(N)], dtype=np.bool)
for _ in range(M):
    i, j, _ = map(int, input().split())
    matrix[i - 1][j - 1] = True

print(connected_components(matrix)[0])

Submission status: Time Limit Exceeded

Solution code:
N,M = [int(i) for i in input().rstrip().split()]
x = c = 0
L = {}
for m in range(M):
    X,Y,Z = [int(i) for i in input().rstrip().split()]
    if (X in L) ^ (Y in L):
        try:
            L[X] = L[Y]
        except:
            L[Y] = L[X]
    elif (X in L) and (Y in L):
        if L[X] != L[Y]:
            for k in [k for k,v in L.items() if v == L[Y]]:
                L[k] = L[X]
            c -= 1
    else:
        x += 1
        c += 1
        L[X] = L[Y] = x

    #print(L)
other = len([v for v in range(1,N+1) if not v in L])
print(c+other)

Submission status: Time Limit Exceeded

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:
        stack = [to_check.pop()]
        cnt += 1
        while stack:
            v = stack.pop()
            checked.add(v)
            to_check -= set([v])
            for u in graph[v]:
                if not u in checked:
                    stack.append(u)
    return cnt

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import connected_components

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

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

matr = matr.tocsr()
print(connected_components(matr, return_labels=False))

Submission status: Time Limit Exceeded

Solution code:
def dfs(aList, visit, node):
    stack = [node]
    visit[node] = True
    while len(stack) != 0:
        current = stack.pop()
        for v in aList[current]:
            if visit[v] == False:
                stack.append(v)
                visit[v] = True


def nomOfConnected(aList, visit):
    counter = 0
    while False in visit:
        counter += 1
        dfs(aList, visit, visit.index(False))
    return counter


n, m = list(map(int, input().split()))
adjacencyList = [[] for i in range(n)]
visit = [False] * n

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

ans = nomOfConnected(adjacencyList, visit)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

Solution code:
import sys

sys.setrecursionlimit(100000)

def visit_tree(now, num):
    if not visited[now]:
        visited[now] = num
        for i in range(len(tree[now])):
            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: Time Limit Exceeded

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]:
            gone[w] = True
            stack.append(w)

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

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    global gone
    dist = [-1] * (n+1)
    stack = [v]
    dist[v] = 0
    gone[v] = True
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            gone[w] = True
            stack.append(w)

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

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    global gone
    dist = [-1] * (n+1)
    stack = [v]
    dist[v] = 0
    gone[v] = True
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            gone[w] = True
            stack.append(w)

n,m = map(int,input().split())
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)

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

n, m = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(m):
    tx, ty, _tz = list(map(int, input().split()))
    edges[tx-1].append(ty-1) 
    edges[ty-1].append(tx-1) 
visited = [False] * n
ans = 0
for i in range(n):
    if not visited[i]:
        q = [i]
        visited[i] = True
        while q:
            u = q.pop(0)
            for v in edges[u]:
                if not visited[v]:
                    q.append(v)
                    visited[v] = True
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))

shozoku = {}
pt = 0
for i in range(k):
    a, b, z = list(map(int, input().split(' ')))
    if a not in shozoku and b not in shozoku:
        shozoku[a] = pt
        shozoku[b] = pt
        pt += 1
    elif a in shozoku and b in shozoku:
        keys = []
        for k, v in shozoku.items():
            if v == shozoku[b]:
                keys.append(k)
        for k in keys:
            shozoku[k] = shozoku[a]
    elif a in shozoku:
        shozoku[b] = shozoku[a]
    elif b in shozoku:
        shozoku[a] = shozoku[b]
# print(shozoku)
ans = 0
used = {}
for i in range(1, n+1):
    if i not in shozoku:
        ans += 1
    elif shozoku[i] not in used:
        used[shozoku[i]] = True
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = (map(int,input().split()))
edges = [list(map(int,input().split())) for _ in range(M)]
net = []
hist = []

for edge in edges:
  p0,p1 = edge[0],edge[1]
  if len(net) == 0:
    net.append([p0,p1])    
    hist.append(p0)
    hist.append(p1)
    
  for _ in net:
      if p0 in _ and p1 not in _:
        _.append(p1)
        hist.append(p1)
      elif p1 in _ and p0 not in _:
        _.append(p0)
        hist.append(p0)
      if p0 not in hist and p1 not in hist:
        net.append([p0,p1])
        hist.append(p0)
        hist.append(p1)
        
print(len(net) + N-len(hist))

Submission status: Time Limit Exceeded

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M=map(int,input().split())
XYZ=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
ittenai=[]
for x,y,z in XYZ:
    data[x].append(y)
    data[y].append(x)
    ittenai.append(x)
    ittenai.append(y)


ittenai=set(ittenai)
count=N-len(ittenai)
while ittenai:
    x=list(ittenai)[0]
    stack=deque([x])
    ittenai.remove(x)
    count+=1
    while stack:
        num=stack.popleft()
        for i in data[num]:
            if i in ittenai:
                ittenai.remove(i)
                stack.append(i)
print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

N, M = (int(x) for x in input().split())

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

searched = [False] * N
count = 0
for i in range(N):
	if searched[i] == True:
		continue

	count += 1
	stack = [i]
	while len(stack) > 0:
		node = stack.pop()
		searched[node] = True
		for n in adj_list[node]:
			if searched[n] == False:
				stack.append(n)

print(count)

Submission status: Time Limit Exceeded

Solution code:


def dfs(graph,s):
    visited=[s]
    S=[s]
    while len(S)>0:
        v=S.pop(0)
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                S.append(w)
    return visited

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    adj={i+1:[] for i in range(N)}
    for l in LIST:
        x,y,z=l[0],l[1],l[2]
        if x not in adj[y]:
            adj[y].append(x)
        if y not in adj[x]:
            adj[x].append(y)
    connected=[]
    count=0

    for i in range(1,N+1):
        if i in connected:
            continue
        else:
            connected+=dfs(adj,i)
            count+=1

    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

def unite(a, b):
    root_a = find_root(a)
    parent[a] = root_a
    root_b = find_root(b)
    parent[b] = root_b
    if root_a != root_b:
        parent[root_b] = root_a

def find_root(a):
    while parent[a] != a:
        a = parent[a]
    return a


for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

def unite(a, b):
    root_a = find_root(a)
    parent[a] = root_a
    root_b = find_root(b)
    parent[b] = root_b
    if root_a != root_b:
        parent[root_b] = root_a

def find_root(a):
    while parent[a] != a:
        a = parent[a]
    return a


for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
already = set()
cnt = 0
ls = []
parent = [i for i in range(n)]

def unite(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    if root_a != root_b:
        parent[root_b] = root_a

def find_root(a):
    while parent[a] != a:
        a = parent[a]
    return a


for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

cnt = 0
_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
already = set()
cnt = 0
ls = []
parent = [i for i in range(n)]

def unite(a, b):
    if not is_same(a, b):
        parent[find_root(b)] = find_root(a)

def find_root(a):
    while parent[a] != a:
        a = parent[a]
    return a

def is_same(a, b):
    return find_root(a) == find_root(b)

for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

cnt = 0
_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))

Submission status: Time Limit Exceeded

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

def main():
    n, m = map(int, input().split())
    memo = set(list(range(n)))
    E = [[] for i in range(n)]
    for i in range(m):
        x, y, z = map(int, input().split())
        E[x-1].append(y-1)
        E[y-1].append(x-1)
    def dfs(cur, pre):
        if pre != -1:
            memo.remove(cur)
        for e in E[cur]:
            if e != pre and e in memo:
                dfs(e, cur)
    ans = 0
    while len(memo):
        cur = memo.pop()
        dfs(cur, -1)
        ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
memo = set(list(range(n)))
E = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
def dfs(cur, pre):
    if pre != -1:
        memo.remove(cur)
    for e in E[cur]:
        if e != pre and e in memo:
            dfs(e, cur)
ans = 0
while len(memo):
    cur = memo.pop()
    dfs(cur, -1)
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n + 1)]
for i in range(m):
    x, y, z = map(int,input().split())
    adjacent_list[x].append(y)
    adjacent_list[y].append(x)
##結局、グラフが何個あるか数える
finished = set()
ans = 0
def dfs(node):
    global finished
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)

while len(finished) != n:
    for i in range(1,n+1):
        if i not in finished:
            dfs(i)
            ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#17:11
inf = 10 ** 10
n,m = map(int,input().split())
pre = [inf for i in range(n)]
ans = n
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  X = [x]
  Y = [y]
  while pre[x] != inf:
    X.append(x)
    x = pre[x]
  while pre[y] != inf:
    Y.append(y)
    y = pre[y]
  if x != y:
    ans -= 1
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
    pre[x] = y
#print(pre)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#17:11
inf = 10 ** 18
n,m = map(int,input().split())
pre = [inf for i in range(n)]
ans = n
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  X = [x]
  Y = [y]
  while pre[x] != inf:
    X.append(x)
    x = pre[x]
  while pre[y] != inf:
    Y.append(y)
    y = pre[y]
  if x != y:
    ans -= 1
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
    pre[x] = y
#print(pre)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#17:11
n,m = map(int,input().split())
pre = [-1 for i in range(n)]
ans = n
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  X = [x]
  Y = [y]
  while pre[x] != -1:
    X.append(x)
    x = pre[x]
  while pre[y] != -1:
    Y.append(y)
    y = pre[y]
  if x != y:
    ans -= 1
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
    pre[x] = y
#print(pre)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#17:11
n,m = map(int,input().split())
pre = [-1 for i in range(n)]
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  X = 0
  while pre[x] != -1:
    X += 1
    x = pre[x]
  Y = 0
  while pre[y] != -1:
    Y += 1
    y = pre[y]
  if x != y:
    if X > Y:
      pre[x] = y
    else:
      pre[y] = x
father = set()
ans = 0
for i in range(n):
  if pre[i] == -1:
    ans += 1
#print(pre)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#17:11
n,m = map(int,input().split())
pre = [-1 for i in range(n)]
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  while pre[x] != -1:
    x = pre[x]
  while pre[y] != -1:
    y = pre[y]
  if x != y:
    pre[x] = y
father = set()
ans = 0
for i in range(n):
  if pre[i] == -1:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

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

def dfs(now,color):
    for y in path[now]:
        if clasta[y] == -1:
            clasta[y] = color
            dfs(y,color)
            
ans = 0
for idx,i in enumerate(clasta):
    if i == -1:
        clasta[idx] = idx
        if path[idx]:
            dfs(idx,idx)
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

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

def dfs(now,color):
    for y in path[now]:
        if clasta[y] == -1:
            clasta[y] = color
            dfs(y,color)

for idx,i in enumerate(clasta):
    if i == -1:
        clasta[idx] = idx
        dfs(idx,idx)

print(len(set(clasta)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        E[x].append(y)
        E[y].append(x)

    visited=[0]*n
    def dfs(v,p)->bool:
        if(visited[v]):
            return False
        visited[v]=1
        for nv in E[v]:
            if(nv==p): continue
            dfs(nv,v)
        return True

    ans=0
    for v in range(n):
        ans+=dfs(v,-1)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
A = [[] for i in range(n+1)]
CHK = [False for i in range(n+1)]
for i in range(m):
  x,y,z = map(int,input().split())
  z = z%2
  if z==0:
    A[x].append(y)
    A[y].append(x)
  else:
    A[x].append(-y)
    A[y].append(-x)
ans = 0
for i in range(1,n+1):
  if CHK[i]:
    continue
  a = A[i]
  if len(a)==0:
    ans+=1
    CHK[i] = True
  else:
    Q=[i]
    while len(Q)>0:
      q = Q.pop()
      P = A[q]
      for p in P:
        p = -p if p<0 else p
        if not CHK[p]:
          Q.append(p)
      CHK[q] = True
    ans+=1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
from collections import deque

input = sys.stdin.readline
def dfs(start, G):
    stack = deque()
    stack.append(start)
    visited = [0]*len(G)
    while stack:
        label = stack.pop()
        visited[label-1]= 1
        for i in G[label-1]:
          if not visited[i-1]:
            #visited[label-1]= 1
            stack.append(i)
    return visited    
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0
visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    v_temp = dfs(i,G)
    visit = np.logical_or(visit, v_temp)
  else:
    visit[i-1] = 1
  count += 1
 
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def dfs(start, G):
    stack = [start]
    visited = [0]*len(G)
    while stack:
        label = stack.pop(0)
        visited[label-1]= 1
        for i in G[label-1]:
          if not visited[i-1]:
            #visited[label-1]= 1
            stack.append(i)
    return visited    
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0
visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    v_temp = dfs(i,G)
    visit = np.logical_or(visit, v_temp)
  else:
    visit[i-1] = 1
  count += 1
 
 
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def dfs(start, G):
    stack = [start]
    visited = [0]*len(G)
    while stack:
        label = stack.pop(0)
        visited[label-1]= 1
        for i in G[label-1]:
          if not visited[i-1]:
            #visited[label-1]= 1
            stack.append(i)
    return visited    

N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)

count = 0
visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    v_temp = dfs(i,G)
    visit = np.logical_or(visit, v_temp)
  else:
    visit[i-1] = 1
  count += 1


print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def dfs(start, G):
    stack = [start]
    visited = [0]*len(G)
    while stack:
        label = stack.pop(0)
        visited[label-1]= 1
        for i in G[label-1]:
          if not visited[i-1]:
            #visited[label-1]= 1
            stack.append(i)
    return visited    

N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)


count = 0
visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  v_temp = dfs(i,G)
  count += 1
  visit = np.logical_or(visit, v_temp)
  
  
print(count)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  n,m=map(int,input().split())
  res=[0]*n

  datas=[None]*m
  for i in range(m):
    x,y,z=map(int,input().split())
    datas[i]=[min(x-1,y-1),max(x-1,y-1)]

  datas=sorted(datas,key=lambda x:x[0])

  maxi=0
  for i in range(len(datas)):
    d=datas[i]
    if res[d[0]]==0 and res[d[1]]==0:
      maxi+=1
      res[d[0]]=maxi
      res[d[1]]=maxi
    elif res[d[0]]==0 and res[d[1]]!=0:
      res[d[0]]=res[d[1]]
    elif res[d[0]]!=0 and res[d[1]]==0:
      res[d[1]]=res[d[0]]
    elif res[d[0]]!=res[d[1]]:
      cor=min(res[d[0]],res[d[1]])
      dum=max(res[d[0]],res[d[1]])
      res[d[0]],res[d[1]]=cor,cor
      for i in range(len(res)):
        if res[i]==dum:
          res[i]=cor

  count0=res.count(0)
  ress=set(res)

  print(count0 + len(ress) - (1 if 0 in ress else 0))
  
solve()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
res=[0]*n

datas=[None]*m
for i in range(m):
  x,y,z=map(int,input().split())
  datas[i]=[min(x-1,y-1),max(x-1,y-1)]

datas=sorted(datas,key=lambda x:x[0])

maxi=0
for i in range(len(datas)):
  d=datas[i]
  if res[d[0]]==0 and res[d[1]]==0:
    maxi+=1
    res[d[0]]=maxi
    res[d[1]]=maxi
  elif res[d[0]]==0 and res[d[1]]!=0:
    res[d[0]]=res[d[1]]
  elif res[d[0]]!=0 and res[d[1]]==0:
    res[d[1]]=res[d[0]]
  elif res[d[0]]!=res[d[1]]:
    cor=min(res[d[0]],res[d[1]])
    dum=max(res[d[0]],res[d[1]])
    res[d[0]],res[d[1]]=cor,cor
    for i in range(len(res)):
      if res[i]==dum:
        res[i]=cor

count0=res.count(0)
ress=set(res)

print(count0 + len(ress) - (1 if 0 in ress else 0))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
res=[0]*n

datas=[None]*m
for i in range(m):
  x,y,z=map(int,input().split())
  datas[i]=[min(x-1,y-1),max(x-1,y-1)]

maxi=0
for i in range(len(datas)):
  d=datas[i]
  if res[d[0]]==0 and res[d[1]]==0:
    maxi+=1
    res[d[0]]=maxi
    res[d[1]]=maxi
  elif res[d[0]]==0 and res[d[1]]!=0:
    res[d[0]]=res[d[1]]
  elif res[d[0]]!=0 and res[d[1]]==0:
    res[d[1]]=res[d[0]]
  elif res[d[0]]!=res[d[1]]:
    cor=min(res[d[0]],res[d[1]])
    dum=max(res[d[0]],res[d[1]])
    res[d[0]],res[d[1]]=cor,cor
    for i in range(len(res)):
      if res[i]==dum:
        res[i]=cor

count0=res.count(0)
ress=set(res)

print(count0 + len(ress) - (1 if 0 in ress else 0))

Submission status: Time Limit Exceeded

Solution code:
import collections

def main():
    n,m = map(int,input().split())
    f = [False for _ in range(n)]
    a = [[] for _ in range(n)]
    res = 0

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

    for i in range(n):
        if not f[i]:
            res += 1
            q=collections.deque()
            q.append(i)
            while q:
                t = q.pop()
                f[t] = True
                for g in a[t]:
                    if not f[g]:
                        q.append(g)
    print(res)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m = map(int,input().split())
    f = [False for _ in range(n)]
    a = [[] for _ in range(n)]
    res = 0

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

    for i in range(n):
        if not f[i]:
            res += 1
            q=[]
            q.append(i)
            while q:
                t = q.pop()
                f[t] = True
                for g in a[t]:
                    if not f[g]:
                        q.append(g)
    print(res)
main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0


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

for i in range(n):
    if not f[i]:
        res += 1
        q=[]
        q.append(i)
        while q:
            t = q.pop()
            f[t] = True
            for g in a[t]:
                if not f[g]:
                    q.append(g)
print(res)

Submission status: Time Limit Exceeded

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

class union:
    def __init__(self,num):
        self.par=[-1]*num
    def get_par(self,node):
        if self.par[node]==-1:
            return node
        else:
            x=self.get_par(self.par[node])
            return x
    def merge(self,x,y):
        X=self.get_par(x)
        Y=self.get_par(y)
        if X!=Y:
            self.par[Y]=X
    def output(self):
        print(self.par)
    def count(self):
        print(self.par.count(-1))
u=union(n)
for i in range(m):
    u.merge(a[i][0],a[i][1])
u.count()

Submission status: Time Limit Exceeded

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

class union:
    def __init__(self,num):
        self.par=[-1]*num
    def get_par(self,node):
        if self.par[node]==-1:
            return node
        else:
            return self.get_par(self.par[node])
    def merge(self,x,y):
        X=self.get_par(x)
        Y=self.get_par(y)
        if X!=Y:
            self.par[Y]=X
    def output(self):
        print(self.par)
    def count(self):
        print(self.par.count(-1))
u=union(n)
for i in range(m):
    u.merge(a[i][0],a[i][1])
u.count()

Submission status: Time Limit Exceeded

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


def dfs(v, visited, G):
    visited[v] = True
    for nv in G[v]:
        if visited[nv]==False:
            dfs(nv, visited, G)


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y, z = map(int, input().split())
        G[x-1].append(y-1)
        G[y-1].append(x-1)
    
    nodes = list(range(N))
    visited = [False]*N
    ans = 0
    while len(nodes)!=0:
        v = nodes.pop()
        if visited[v]==True:
            continue
        ans += 1
        dfs(v, visited, G)
        # print(visited)
        # print(nodes)
    
    print(ans)



if __name__ == '__main__':
    main()