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:
#!/usr/bin/env python3

import sys

sys.setrecursionlimit(1000000)

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

# D[i][j]: Card i has a rel. with card j
D = [[] for i in range(N)]
for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    D[x].append(y)
    D[y].append(x)

visited = [False for i in range(N)]
def dfs(n):
    for idx in D[n]:
        if not visited[idx]:
            visited[idx] = True
            dfs(idx)

cnt = 0
for n in range(N):
    if not visited[n]:
        visited[n] = True
        dfs(n)
        cnt += 1
print(cnt)

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].copy())
		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=[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].copy())
		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 = (int(x) for x in input().split())
list = [[None]*3 for i in range(M)]
for i in range (M):
    index = 0
    for x in input().split():
        list[i][index] = int(x)
        index += 1

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

conn_blocks = []
conn_blocks.append([X[0], Y[0]])
index_list = [X[0], 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]])
    index_list.append(X[i])
    index_list.append(Y[i])

counter = 0
for i in range(1, N+1):
    if i not in index_list:
        counter += 1

print(len(conn_blocks)+counter)

Submission status: Time Limit Exceeded

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

X,Y,Z = map(int,input().split())
L[X-1] = 1
L[Y-1] = 1 
b = 1

if M == 1:
    print(N-1)
else:
    for i in range(M-1):
        X,Y,Z = map(int,input().split())
        if L[X-1] != 0 and L[Y-1] != 0:
            if L[X-1] != L[Y-1]:
                a = min(L[X-1],L[Y-1])
                for c in L:
                    if c == max(L[X-1],L[Y-1]):
                        c = a
        elif L[X-1] != 0 and L[Y-1] == 0:
            L[Y-1] = L[X-1]
        elif L[X-1] == 0 and L[Y-1] != 0:
            L[X-1] = L[Y-1]
        else:
            b += 1
            L[X-1] = b
            L[Y-1] = b

    L = list(set(L))
    l = len(L)

    print(l)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
grid = []
for i in range(m):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)

ren = [[grid[0][0],grid[0][1]]]
count = 0

for i in range(m):
    for j in range(len(ren)):
        if grid[i][0] in ren[j] or grid[i][1] in ren[j]:
            ren[j].extend([grid[i][0],grid[i][1]])
            count = 1
        else:
            pass
    if count == 1:
        pass
        count = 0
    else:
        ren.append([grid[i][0], grid[i][1]])
        count = 0

for i in range(1,n+1):
    for j in range(len(ren)):
        if i in ren[j]:
            count = 1
    if count == 1:
        count = 0
    else:
        ren.append([i])
        count = 0



print(len(ren))

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
xyz=[]
for i in range(m):
    xyz.append(list(map(int,input().split())))
a=[[]]
a[0].append(xyz[0][0])
a[0].append(xyz[0][1])
for i in range(m):
    t = False
    for j in range(len(a)):
        if xyz[i][0] in a[j]:
            t = t or True
            if not(xyz[i][1] in a[j]):
                a[j].append(xyz[i][1])
        elif xyz[i][1] in a[j]:
            a[j].append(xyz[i][0])
    if not(t):
        a.append([xyz[i][0],xyz[i][1]])
print(len(a)+n-sum(len(i) for i in a))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M=map(int, input().split())
g = np.zeros(N).astype(int)
for m in range(M):
    x,y,z=map(int, input().split())
    x -= 1
    y -= 1
    if g[x] == 0 and g[y] == 0:
        g[x] = m+1
        g[y] = m+1
    elif g[x] == 0:
        g[x] = g[y]
    elif g[y] == 0:
        g[y] = g[x]
    elif g[x] == g[y]:
        pass
    else:
        t = g[x]
        g[np.where(g==g[y])] = t
cnt = np.zeros(M)
ans = 0
for mm in g:
    m = mm-1
    if m < 0:
        ans += 1
    elif cnt[m] == 0:
        ans += 1
        cnt[m] = 1
print(ans)

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 or Y[i] in g:
			g.append(X[i])
			g.append(Y[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

import math
import re

def main(params):
    n = int(params[0])
    m = int(params[1])
    xyz = params[2:]
    results = {}
    tmp = {}
    for i in xyz:
        x,y,z = i.split()
        x = int(x)
        y = int(y)
        z = int(z)
        if x in results and y in results:
            if results[x] != results[y]:
                t = results[y]
                for k in results:
                    if results[k] == t:
                        results[k] = results[x]
        elif x not in results and y in results:
            results[x] = results[y]
        elif x in results and y not in results:
            results[y] = results[x]
        elif x not in results and y not in results:
            results[x] = x
            results[y] = x
    t = {}
    for i in range(n):
        if i+1 in results:
            t[results[i+1]] = 1
        else:
            t[i+1] = 2
    print len(t)

if __name__ == "__main__":
    n,m = raw_input().split()
    n = int(n)
    m = int(m)
    cnt = m # TODO: edit here
    params = [n,m]
    for i in range(cnt):
        param = raw_input()
        params.append(param)
    main(params)

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:
from math import *



class V:
    def __init__(self,si,parent):
        self.si = si
        self.parent = parent
    def isInnovator(self):
        return self.parent is None
    def findInnovator(self):
        re = self
        while True:
            if re.parent is None:
                return re
            re = re.parent


N,K = tuple(map(int,input().split()))
vs = [V(vi,None) for vi in range(N)]

for _ in range(K):
    ui,vi,w = tuple(map(int,input().split()))
    ui-=1
    vi-=1
    u = vs[ui]
    v = vs[vi]
    uInnov = u.findInnovator()
    vInnov = v.findInnovator()
    if uInnov == vInnov:
        continue
    vInnov.parent = uInnov

re = 0
for v in vs:
    if v.isInnovator():
        re += 1

print(re)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, m = map(int, input().split())

    edges = [[] for _ in range(n)]
    for _ in range(m):
        x, y, _ = map(int, input().split())
        edges[x-1].append(y-1)
        edges[y-1].append(x-1)
    
    print(count_graph(edges, n))

def count_graph(edges, n):
    unvisited = set(range(n))
    c = 0

    while unvisited:
        f = first(unvisited)
        unvisited.remove(f)
        c += 1

        q = deque()
        q.append(f)
        while q:
            u = q.popleft()
            for v in edges[u]:
                if v in unvisited:
                    q.append(v)
                    unvisited.remove(v)
    
    return c

def first(s):
    for x in s:
        return x

main()

Submission status: Time Limit Exceeded

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

for i in range(M):
    x,y,z = map(int,input().split())
    if x != card[x-1]:  x = card[x-1]
    a = card[y-1]
    for i in range(card.count(a)):
        card[card.index(a)] = x

print(len(set(card)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M=map(int, input().split())
g = np.zeros(N).astype(int)
for m in range(M):
    x,y,z=map(int, input().split())
    x -= 1
    y -= 1
    if g[x] == 0 and g[y] == 0:
        g[x] = m+1
        g[y] = m+1
    elif g[x] == 0:
        g[x] = g[y]
    elif g[y] == 0:
        g[y] = g[x]
    elif g[x] == g[y]:
        pass
    else:
        t = g[x]
        for n in range(N):
            if g[n] == g[y]:
                g[n] = t
cnt = np.zeros(M)
ans = 0
for mm in g:
    m = mm-1
    if m < 0:
        ans += 1
    if cnt[m] == 0:
        ans += 1
        cnt[m] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
X, Y = [], []
# vertex table
V = [[] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    V[x-1].append(y)
    V[y-1].append(x)

# search connection
con = 0
remain = [i for i in range(1, N+1)]
while len(remain) > 0:
    con += 1
    v = remain[0]
    search = set()
    search.add(v)
    while len(search) > 0:
        v = search.pop()
        remain.remove(v)
        for u in V[v-1]:
            if u in remain:
                search.add(u)

print(con)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

#import numpy as np
#import scipy, scipy.special

# Python 3 modules: https://docs.python.org/3/library/

import sys
import math, itertools, operator
from math import *
from math import factorial as fact
from itertools import permutations, combinations
from functools import reduce
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5
from fractions import gcd

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(inp = input, sep = ' ', conv = int):
    return map(conv, inp().split(sep = sep))

################################################################################

sys.setrecursionlimit(1000000)

N, M = input_ints()

# D[i][j]: Card i has a rel. with card j
D = [[] for i in range(N)]
for i in range(M):
    x, y, z = input_ints()
    x -= 1
    y -= 1
    D[x].append(y)
    D[y].append(x)

visited = [False for i in range(N)]
def dfs(n):
    for idx in D[n]:
        if not visited[idx]:
            visited[idx] = True
            dfs(idx)

cnt = 0
for n in range(N):
    if not visited[n]:
        visited[n] = True
        dfs(n)
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq

def initialize(value, n):
    return [value]*n

class Graph:
    def __init__(self, n_vertices, edge_list, directed=True):
        self.n_vertices = n_vertices
        self.edge_list = edge_list
        self.directed = directed
        self.n_component = None

        self.V = [Vertex(i) for i in range(n_vertices)]
        self.E = []

        if directed:
            for i, e in enumerate(edge_list):
                tail, head = self.V[e[0]], self.V[e[1]]
                edge = Edge((tail, head), i)
                self.E.append(edge)
                tail.incident.append(edge)
                tail.out_neighbor.append(head)
                head.in_neighbor.append(tail)
            self.n_edges = len(self.E)

        else:
            i = 0
            for e in edge_list:
                tail, head = self.V[e[0]], self.V[e[1]]
                edge = Edge((tail, head), i)
                self.E.append(edge)
                tail.incident.append(edge)
                tail.out_neighbor.append(head)
                head.in_neighbor.append(tail)
                i += 1

                edge = Edge((head, tail), i)
                self.E.append(edge)
                head.incident.append(edge)
                head.out_neighbor.append(tail)
                tail.in_neighbor.append(head)
                i += 1
            self.n_edges = len(self.E)//2

    def __str__(self):
        return "a graph with {0} vertices and {1} edges".format(self.n_vertices, self.n_edges)

    def underlying_graph(self):
        if self.directed:
            return Graph(self.n_vertices, self.edge_list, directed=False)
        else:
            return self
    
    def indeg(self, v):
        return len(v.in_neighbor)

    def outdeg(self, v):
        return len(v.out_neighbor)
    
    def set_vertex_value(self, value_dict):
        for v_name, val_list in value_dict.items():
            for i, v in enumerate(self.V):
                v.set_value(v_name, val_list[i])
    
    def calc_component(self):
        # find the component of a graph by DFS.
        g = self.underlying_graph()
        comp = [None]*self.n_vertices
        counter = 0

        while None in comp:
            idx = comp.index(None)
            for i in g.DFS(idx):
                comp[i] = counter
            counter += 1

        self.n_components = counter

        return comp
    
    def DFS(self, init_idx=0):
        init = {'DFS': initialize(None, self.n_vertices),
                'DFS order': initialize(None, self.n_vertices)}
        self.set_vertex_value(init)

        s = self.V[init_idx]
        length = 0

        stck = []
        stck.append((s, length))
        visited = []
        finished = []
        counter = 0

        while stck:
            v, l = stck.pop()

            if v['DFS'] is not None:
                continue
            visited.append(v.idx)
            v['DFS'] = l
            v['DFS order'] = counter
            counter += 1

            all_visited = True
            for u in v.out_neighbor:
                if u['DFS'] is None:
                    all_visited = False
                    stck.append((u, l+1))

            if all_visited:
                finished.append(visited.pop())

        while len(visited) != 0:
            finished.append(visited.pop())

        return finished

class Vertex(dict):
    def __init__(self, idx):
        self.idx = idx
        self.in_neighbor = []
        self.out_neighbor = []
        self.incident = []
        self.component = None

    def __eq__(self, other):
        if not isinstance(other, Vertex):
            return NotImplemented
        return self.idx == other.idx

    def __lt__(self, other):
        if not isinstance(other, Vertex):
            return NotImplemented
        return self.idx < other.idx

    def __ne__(self, other):
        return not self.__eq__(other)

    def __le__(self, other):
        return self.__lt__(other) or self.__eq__(other)

    def __gt__(self, other):
        return not self.__le__(other)

    def __ge__(self, other):
        return not self.__lt__(other)

    def __str__(self):
        return "vertex {}".format(self.idx)

    def set_value(self, val_name, value):
        self[val_name] = value


class Edge(dict):
    def __init__(self, ends, idx):
        self.tail = ends[0]
        self.head = ends[1]
        self.ends = list(ends)
        self.idx = idx

    def __eq__(self, other):
        if not isinstance(other, Edge):
            return NotImplemented
        return self.idx == other.idx

    def __lt__(self, other):
        if not isinstance(other, Edge):
            return NotImplemented
        return self.idx < other.idx

    def __ne__(self, other):
        return not self.__eq__(other)

    def __le__(self, other):
        return self.__lt__(other) or self.__eq__(other)

    def __gt__(self, other):
        return not self.__le__(other)

    def __ge__(self, other):
        return not self.__lt__(other)

    def __str__(self):
        if self.idx is None:
            return "edge ({0}, {1})".format(self.tail, self.head)
        else:
            return "edge {0}: ({1}, {2})".format(self.idx, self.tail, self.head)

    def is_selfloop(self):
        if self.tail == self.head:
            return True
        else:
            return False

    def set_value(self, val_name, value):
        self[val_name] = value

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

g = Graph(N, info, directed=False)
g.calc_component()

print(g.n_components)

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(h) for h in input().split()]
q=[]
for i in range(M):
  q.append(set([int(h) for h in input().split()[0:2]]))

count=0

while count!=10000:
    a=q.pop()
    for j in q:
        if len(j&a) != 0:
            j |=a
            count=0
            break
    else:q=[a]+q
    if count>len(q): break
    count+=1

ans=0
for qi in q:
  ans+=len(qi)
print(N-ans+len(q))

Submission status: Time Limit Exceeded

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

nodes = [x for x in range(1, n+1)]

for x in range(m):
	x, y, z = map(int, input().split())
	updated_nodes = [nodes[x-1] if ele == nodes[y-1] else ele for ele in nodes]
	nodes = updated_nodes
	
nodes_set = set(nodes)
print(len(nodes_set))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(m)]
nexts = {}
for x, y, z in data:
    nexts.setdefault(x, [])
    nexts[x].append(y)
    nexts.setdefault(y, [])
    nexts[y].append(x)
done = {}
for i in nexts.keys():
    done[i] = False
ans = n
for i in nexts.keys():
    if done[i]:
        continue
    queue = [i]
    done[i] = True
    s = set()
    while len(queue) > 0:
        j = queue.pop(0)
        s.add(j)
        done[j] = True
        for k in nexts[j]:
            if not done[k]:
                queue.append(k)
    ans -= len(s) - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split(' '))
hints = []
nums = set()
for _ in range(m):
    x, y, z = map(int, input().split(' '))
    s = {x, y}
    nums = nums | s
    processed = False
    for idx, hint in enumerate(hints):
        if len(hint & s) > 0:
            hints[idx] = hint | s
            processed = True

    if not processed:
        hints.append(s)

cost = len(hints)
cleared = sum(map(len, hints))
cost += n - cleared
print(cost)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import math
import re

def main(params):
    n = int(params[0])
    m = int(params[1])
    xyz = params[2:]
    results = {}
    for i in xyz:
        x,y,z = i.split()
        x = int(x)
        y = int(y)
        z = int(z)
        if x not in results and y not in results:
            results[x] = x
            results[y] = x
        elif x not in results and y in results:
            results[x] = results[y]
        elif x in results and y not in results:
            results[y] = results[x]
        elif x in results and y in results:
            if results[x] != results[y]:
                t = results[y]
                for k in results:
                    if results[k] == t:
                        results[k] = results[x]
    t = {}
    for i in range(n):
        if i+1 in results:
            t[results[i+1]] = 1
        else:
            t[i+1] = 2
    print len(t)

if __name__ == "__main__":
    n,m = raw_input().split()
    n = int(n)
    m = int(m)
    cnt = m # TODO: edit here
    params = [n,m]
    for i in range(cnt):
        param = raw_input()
        params.append(param)
    main(params)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc126/tasks/abc126_e
import itertools
from collections import Counter
from collections import defaultdict
import bisect


# Union find
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _ in range(size)]  # 負の値の場合根を表す。正の値は次の要素を返す、根まで続く

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

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

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                #self.table[s1] += -1
                self.table[s2] = s1
        return

    def num_group(self):
        # print(self.table)
        return self.table.count(-1)


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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

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

arrival = [-1 for i in range(n+1)]
arrivalcounter = 0
counter = 1
q = [1]
temp = 2
while arrivalcounter < n:
    if len(q) == 0:
        counter += 1
        while arrival[temp] != -1:
            temp += 1
        q.append(temp)

    arrival[q[0]] = 1 #訪問済み
    arrivalcounter += 1

    while len(q) != 0:
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i]] == -1:
                arrival[graph[q[0]][i]] = 1
                arrivalcounter += 1
                q.append(graph[q[0]][i])
        q.pop(0)
print(counter)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc126/tasks/abc126_e
import itertools
from collections import Counter
from collections import defaultdict
import bisect


# Union find
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _ in range(size)]  # 負の値の場合根を表す。正の値は次の要素を返す、根まで続く
        self.size = [1 for _ in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

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

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.size[s1] += self.size[s2]
                else:
                    self.table[s1] = s2
                    self.size[s2] += self.size[s1]
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                #self.table[s1] += -1
                self.table[s2] = s1
                self.size[s1] += self.size[s2]
        return

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

    def num_group(self):
        # print(self.table)
        return self.table.count(-1)


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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M=map(int, input().split())
g = np.zeros(N).astype(int)
for m in range(M):
    x,y,z=map(int, input().split())
    x -= 1
    y -= 1
    if g[x] == 0 and g[y] == 0:
        g[x] = m+1
        g[y] = m+1
    elif g[x] == 0:
        g[x] = g[y]
    elif g[y] == 0:
        g[y] = g[x]
    else:
        t = g[x]
        for n in range(N):
            if g[n] == g[y]:
                g[n] = t
cnt = np.zeros(M)
ans = 0
for mm in g:
    m = mm-1
    if m < 0:
        ans += 1
    if cnt[m] == 0:
        ans += 1
        cnt[m] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

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

arrival = [-1 for i in range(n+1)]
arrivalcounter = 0
counter = 1
q = [1]
qcounter = 1
temp = 2
while arrivalcounter < n:
    if qcounter == 0:
        counter += 1
        while arrival[temp] != -1:
            temp += 1
        q.append(temp)
        qcounter += 1

    arrival[q[0]] = 1 #訪問済み
    arrivalcounter += 1

    while qcounter != 0:
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i]] == -1:
                arrival[graph[q[0]][i]] = 1
                arrivalcounter += 1
                q.append(graph[q[0]][i])
                qcounter += 1
        q.pop(0)
        qcounter -= 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, XYZ):
    g = defaultdict(dict)
    for x, y, z in XYZ:
        g[x][y] = z % 2
        g[y][x] = z % 2

    ans = 0
    done = set()
    for i in range(1, N+1):
        if i in done:
            continue
        ans += 1
        q = deque([i])
        while q:
            u = q.popleft()
            done.add(u)
            for v in g[u]:
                if v not in done:
                    q.append(v)
    return ans


def main():
    # N = read_int()
    N, M = read_int_n()
    XYZ = [read_int_n() for _ in range(M)]
    print(slv(N, M, XYZ))

    # N = 10**5
    # XYZ = [random.randint()]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,input().split())
Link=[[] for i in range(N)]
for i in range(M):
    X,Y,Z=map(lambda x:int(x)-1,input().split())
    Link[X].append(Y)
    Link[Y].append(X)
queue=deque()
queue.append(0)
went=[0]*N
wentnum=0
island=0
while wentnum!=N:
    for n,j in enumerate(went):
        if not j:
            island+=1
            went[n]=island
            wentnum+=1
            queue.append(n)
            break
    while queue:
        cur=queue.pop()
        for togo in Link[cur]:
            if not went[togo]:
                went[togo]=island
                wentnum+=1
                queue.append(togo)
print(island)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

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

arrival = [-1 for i in range(n+1)]
arrivalcounter = 0
counter = 1
q = [1]
temp = 2
while arrivalcounter < n:
    if len(q) == 0:
        counter += 1
        while arrival[temp] != -1:
            temp += 1
        q.append(temp)

    arrival[q[0]] = 1 #訪問済み
    arrivalcounter += 1

    while len(q) != 0:
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i]] == -1:
                arrival[graph[q[0]][i]] = 1
                arrivalcounter += 1
                q.append(graph[q[0]][i])
        q.pop(0)
print(counter)