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:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

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

#強連結成分分解
#label：グループ数
#group[i]：i個目のノードが所属するグループ
def scc(N, G, RG):
    used = [False]*N
    group = [None]*N
    order = []
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    for i in range(N):
        if not used[i]:
            dfs(i)
    def rdfs(S,col):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in RG[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            group[v1] = col
    used = [False]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs([s], label)
            label += 1
    return label, group

N,M = II()
X,Y,Z = Line(M,3)

graph = [[] for _ in range(N)]
for i in range(M):
    graph[X[i]-1].append(Y[i]-1)
    graph[Y[i]-1].append(X[i]-1)

label,group = scc(N,graph,graph)
print(label)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

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

#強連結成分分解
#label：グループ数
#group[i]：i個目のノードが所属するグループ
def scc(N, G, RG):
    order = []
    used = [0]*N
    group = [None]*N
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
    for i in range(N):
        if not used[i]:
            dfs(i)
    used = [0]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
    return label, group

N,M = II()
X,Y,Z = Line(M,3)

graph = [[] for _ in range(N)]
for i in range(M):
    graph[X[i]-1].append(Y[i]-1)
    graph[Y[i]-1].append(X[i]-1)

label,group = scc(N,graph,graph)
print(label)

Submission status: Time Limit Exceeded

Solution code:
#解説チラ見
n,m = map(int,input().split())
ans = n
pre = [i for i in range(n)]
for _ in range(m):
  x,y,z = map(lambda x: int(x)-1, input().split())
  while pre[x] != x:
    x = pre[x]
  while pre[y] != y:
    y = pre[y]
  if x != y:
    ans -= 1
    pre[x] = y
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
INFTY = 10**10
N,M = map(int,input().split())
G = {}
for _ in range(M):
    x,y,z = map(int,input().split())
    if x not in G:
        G[x]=[]
    G[x].append(y)
    if y not in G:
        G[y]=[]
    G[y].append(x)
cnt = N-len(G)
while G:
    K = len(G)
    d = {i:INFTY for i in G.keys()}
    k = list(G.keys())[0]
    d[k]=0
    hist = {i:0 for i in G.keys()}
    heap = [(0,k)]
    while heap:
        cur = heapq.heappop(heap)
        hist[cur[1]] = 1
        for x in G[cur[1]]:
            if hist[x]==0:
                if d[cur[1]]+1<d[x]:
                    d[x] = d[cur[1]]+1
                    heapq.heappush(heap,(d[x],x))
    A = list(G.keys())
    for i in A:
        if hist[i]==1:
            del G[i]
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    # G = {i: [] for i in range(N)}
    nodes = set()
    G = {}
    for x, y in zip(X, Y):
        x -= 1
        y -= 1
        # print(x, y)
        G.setdefault(x, [])
        G.setdefault(y, [])
        G[x].append(y)
        G[y].append(x)
        nodes |= set([x, y])
    # print(G)
    n = N - len(nodes)
    # print(f'nodes: {nodes}')
    # print(f'n: {n}')

    def dfs(v, p):
        ret = set([v])
        for nv in G[v]:
            if nv in p:
                continue
            else:
                ret |= dfs(nv, p + [v])
        return ret

    # print('あ')

    # n = 0
    while True:
        if not len(G):
            break
        # print(G.keys())
        for node in dfs(list(G.keys())[0], []):
            # print(node)
            del G[node]
        # print(n)
        n += 1

    print(n)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    Z = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    G = {i: [] for i in range(N)}
    for x, y in zip(X, Y):
        x -= 1
        y -= 1
        # print(x, y)
        G[x].append(y)
        G[y].append(x)
    # print(G)

    def dfs(v, p):
        ret = set([v])
        for nv in G[v]:
            if nv in p:
                continue
            else:
                ret |= dfs(nv, p + [v])
        return ret

    # print('あ')

    n = 0
    while True:
        if not len(G):
            break
        # print(G.keys())
        for node in dfs(list(G.keys())[0], []):
            # print(node)
            del G[node]
        # print(n)
        n += 1

    print(n)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    Z = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def dfs(g, start):
    global visit
    visiting = [start]
    while visiting:
        v = visiting.pop()
        visit[v] = True
        for v2 in g.get(v,()):
            if v2 in visit or v2 in visiting:
                continue
            visiting.append(v2)

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

visit = {}
g = {}
for v in range(1,N+1):
    g[v] = []

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

count = 0
for v in range(1,N+1):
    if v in visit:
        continue
    dfs(g,v)
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def dfs(start):
    global visit
    visiting = [start]
    while visiting:
        v = visiting.pop()
        visit[v] = True
        for v2 in g.get(v,()):
            if v2 in visit or v2 in visiting:
                continue
            visiting.append(v2)

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

visit = {}
g = {}
for v in range(1,N+1):
    g[v] = []

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

count = 0
for v in range(1,N+1):
    if v in visit:
        continue
    dfs(v)
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
nl = [[] for _ in range(N + 1)]
for _ in range(M):
    X, Y, Z = map(int, input().split())
    nl[X].append(Y)
    nl[Y].append(X)

seen = set()
ans = 0
stack = list()
for i in range(1, N + 1):
    if i not in seen:
        ans += 1
        stack.append(i)
        while len(stack) > 0:
            v = stack.pop()
            for next_v in nl[v]:
                seen.add(v)
                if next_v not in seen:
                    stack.append(next_v)
print(ans)

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
  X,Y,Z = map(int, input().split())
  X -= 1
  Y -= 1
  G[X].append(Y)
  G[Y].append(X)
#print(G)

def dfs(u,v):
  for t in G[u]:
    #if t != v:
    if not Visited[t]:
      Visited[t] = True
      dfs(t,u)

Visited = [False for _ in range(N)]
ans = 0
for i in range(N):
  if not Visited[i]:
    Visited[i] = True
    ans += 1
    dfs(i,-1)
print(ans)

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
  X,Y,Z = map(int, input().split())
  X -= 1
  Y -= 1
  G[X].append(Y)
  G[Y].append(X)
#print(G)

def dfs(u,v):
  for t in G[u]:
    #if t != v:
    if not Visited[t]:
      Visited[t] = True
      dfs(t,u)

Visited = [False for _ in range(N)]
ans = 0
for i in range(N):
  if not Visited[i]:
    Visited[i] = True
    ans += 1
    dfs(i,-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
n , m = map(int,input().split())
g = [i for i in range(n)]
def find(x):
    if g[x] == x:
        return x
    g[x] = find(g[x])
    return g[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x!=y:
        g[x] = y

for i in range(m):
    xi,yi,zi = map(int,input().split())
    union(xi-1,yi-1)

print(len(set([find(i) for i in range(n)])))

Submission status: Time Limit Exceeded

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

def main():
    n,m = map(int,input().split())
    li = [list(map(int,input().split())) for _ in range(m)]

    roots = [[] for _ in range(n)]
    for x,y,z in li:
        roots[x-1].append(y-1)
        roots[y-1].append(x-1)

    ans = 0
    count = 0
    stack = []
    group = [-1] * n

    while count < n:
        a = group.index(-1)
        stack.append(a)
        group[a] = ans
        count += 1
        while stack:
            label = stack.pop(-1)
            for i in roots[label]:
                if group[i] == -1:
                    group[i] = ans
                    stack.append(i)
                    count += 1
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

G = [set([n]) for n in range(N)]

for m in range(M):
    X, Y, Z = map(int, input().split())
    X   -= 1
    Y   -= 1
    Gx   = G[X]
    Gy   = G[Y]
    Gxy  = Gx | Gy
    for idx in Gxy:
        G[idx] = Gxy

print(len(set([tuple(g) for g in G])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = [ tuple( int(v)-1 for v in input().split() ) for i in range(k) ]

card_list = set(card_list)
for i in card_list:
    p, q = i[0], i[1]
    if card_parent[p] != card_parent[q]:
        union_parent, vanish_parent = min(card_parent[p], card_parent[q]), max(card_parent[p], card_parent[q])
        for j in card_set[vanish_parent]:
            card_parent[j] = union_parent
        card_set[union_parent] = card_set[union_parent] | card_set[vanish_parent]

print(len(set(card_parent)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = sorted( [ [ int(v)-1 for v in input().split() ] for i in range(k) ])

 
for i in card_list:
    p, q = i[0], i[1]
    if card_parent[p] != card_parent[q]:
        union_parent, vanish_parent = min(card_parent[p], card_parent[q]), max(card_parent[p], card_parent[q])
        for j in card_set[vanish_parent]:
            card_parent[j] = union_parent
        card_set[union_parent] = card_set[union_parent] | card_set[vanish_parent]

print(len(set(card_parent)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})


def BFS():
    total=0
    #print(check_node)
    now=min(check_node)
    tmp=[now]
    check_node.remove(now)
    ans=N-len(check_node)
    new_tmp=[]
    while len(check_node)>0:
        #print("tmp:{}".format(tmp))
        if tmp==[]:
            ans+=1
            tmp.append(check_node[0])
            check_node.remove(check_node[0])
        total+=1
        for each in tmp:
            #print("each:{}".format(each))
            for i in node[each].next:
                k=list(i.keys())[0]
                if k in check_node:
                    #print("append :{}".format(k))
                    new_tmp.append(k)
                    check_node.remove(k)
        #print("new_tmp:{}".format(new_tmp))
        #print("check_node:{}".format(check_node))
        tmp=new_tmp
        new_tmp=[]
    #print("end")
    #print("loop time:{}".format(total))
    #print("ans:{}".format(ans))
    print(ans)


def rec_BFS(i):
    tmp=[list(j.keys())[0] for j in i]
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            rec_BFS(node[each].next)






        
        

N,M=list(map(int,input().split()))
node=[Node() for _ in range(N)]
#ans=[[100 for _ in range(N)]for _ in range(N)]
tmp_node=[]
for i in range(M):
    tmp_p,tmp_n,tmp_w=list(map(int,input().split()))
    node[tmp_p-1].get_data(tmp_n-1)
    node[tmp_n-1].get_data(tmp_p-1)

check_node=[i for i in range(N)]
BFS()
"""
check_node=[False for _ in range(N)]
s=0
for i in range(N):
    if not check_node[i]:
        check_node[i]=True
        s+=1
        rec_BFS(node[i].next)
print(s)
"""

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})


def BFS():
    total=0
    check_node=tmp_node
    #print(check_node)
    now=min(check_node)
    tmp=[now]
    check_node.remove(now)
    ans=N-len(check_node)
    new_tmp=[]
    while len(check_node)>0:
        #print("tmp:{}".format(tmp))
        if tmp==[]:
            ans+=1
            tmp.append(check_node[0])
            check_node.remove(check_node[0])
        total+=1
        for each in tmp:
            #print("each:{}".format(each))
            for i in node[each].next:
                k=list(i.keys())[0]
                if k in check_node:
                    #print("append :{}".format(k))
                    new_tmp.append(k)
                    check_node.remove(k)
        #print("new_tmp:{}".format(new_tmp))
        #print("check_node:{}".format(check_node))
        tmp=new_tmp
        new_tmp=[]
    #print("end")
    #print("loop time:{}".format(total))
    #print("ans:{}".format(ans))
    print(ans)


def rec_BFS(i):
    tmp=[list(j.keys())[0] for j in i]
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            rec_BFS(node[each].next)






        
        

N,M=list(map(int,input().split()))
node=[Node() for _ in range(N)]
#ans=[[100 for _ in range(N)]for _ in range(N)]
tmp_node=[]
for i in range(M):
    tmp_p,tmp_n,tmp_w=list(map(int,input().split()))
    if not tmp_p-1 in tmp_node:
        tmp_node.append(tmp_p-1)
    if not tmp_n-1 in tmp_node:
        tmp_node.append(tmp_n-1)
    node[tmp_p-1].get_data(tmp_n-1)
    node[tmp_n-1].get_data(tmp_p-1)
#BFS()
s=0
check_node=[False for _ in range(N)]
for i in range(N):
    if not check_node[i]:
        check_node[i]=True
        s+=1
        rec_BFS(node[i].next)
print(s)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})


def BFS():
    total=0
    check_node=tmp_node
    #print(check_node)
    now=min(check_node)
    tmp=[now]
    check_node.remove(now)
    ans=N-len(check_node)
    new_tmp=[]
    while len(check_node)>0:
        #print("tmp:{}".format(tmp))
        if tmp==[]:
            ans+=1
            tmp.append(check_node[0])
            check_node.remove(check_node[0])
        total+=1
        for each in tmp:
            #print("each:{}".format(each))
            for i in node[each].next:
                k=list(i.keys())[0]
                if k in check_node:
                    #print("append :{}".format(k))
                    new_tmp.append(k)
                    check_node.remove(k)
        #print("new_tmp:{}".format(new_tmp))
        #print("check_node:{}".format(check_node))
        tmp=new_tmp
        new_tmp=[]
    #print("end")
    #print("loop time:{}".format(total))
    #print("ans:{}".format(ans))
    print(ans)


        




        
        

N,M=list(map(int,input().split()))
node=[Node() for _ in range(N)]
#ans=[[100 for _ in range(N)]for _ in range(N)]
tmp_node=[]
for i in range(M):
    tmp_p,tmp_n,tmp_w=list(map(int,input().split()))
    if not tmp_p-1 in tmp_node:
        tmp_node.append(tmp_p-1)
    if not tmp_n-1 in tmp_node:
        tmp_node.append(tmp_n-1)
    node[tmp_p-1].get_data(tmp_n-1)
    node[tmp_n-1].get_data(tmp_p-1)
BFS()

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})


def BFS():
    total=0
    check_node=[i for i in range(0,N)]
    now=0
    tmp=[now]
    check_node.remove(now)
    ans=1
    new_tmp=[]
    while len(check_node)>0:
        #print("tmp:{}".format(tmp))
        if tmp==[]:
            ans+=1
            tmp.append(check_node[0])
            check_node.remove(check_node[0])
        total+=1
        for each in tmp:
            #print("each:{}".format(each))
            for i in node[each].next:
                k=list(i.keys())[0]
                if k in check_node:
                    #print("append :{}".format(k))
                    new_tmp.append(k)
                    check_node.remove(k)
        #print("new_tmp:{}".format(new_tmp))
        #print("check_node:{}".format(check_node))
        tmp=new_tmp
        new_tmp=[]
    #print("end")
    #print("loop time:{}".format(total))
    #print("ans:{}".format(ans))
    print(ans)


        




        
        

N,M=list(map(int,input().split()))
node=[Node() for _ in range(N)]
#ans=[[100 for _ in range(N)]for _ in range(N)]
for i in range(M):
    tmp_p,tmp_n,tmp_w=list(map(int,input().split()))
    node[tmp_p-1].get_data(tmp_n-1)
    node[tmp_n-1].get_data(tmp_p-1)
BFS()

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(100000)
N,M = list(map(int,input().split()))
XYZ = [list(map(int,input().split())) for _ in range(M)]

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

for i in XYZ:
    G[i[0]-1].append(i[1])
    G[i[1]-1].append(i[0])

check = [False for _ in range(N)]#各頂点を訪問したかどうか

def DFS(G,s):
    check[s-1] = True
    for i in G[s-1]:
        if not check[i-1]:
            DFS(G,i)
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

G = [[] for _ in range(N)]
for i in XYZ:
    for j in range(1,N+1):
        if i[0] == j:
            G[j-1].append(i[1])
        if i[1] == j:
            G[j-1].append(i[0])

check = [False for _ in range(N)]#各頂点を訪問したかどうか
def DFS(G,start):
    check[start-1] = True
    for i in G[start-1]:
        if not check[i-1]:
            DFS(G,i)
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    while ds[x] != x:
        x = ds[x]

    ds[x] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False


def main():
    N, M = map(int, input().split())
    ds = {}

    for i in range(N):
        dsMakeSet(ds, i+1)

    n = 0
    for i in range(M):
        X,Y,Z = map(int, input().split())
        if dsUnion(ds, X, Y):
            n += 1
        
    print(N - n)
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    while ds[x] != x:
        x = ds[x]

    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False


def main():
    N, M = map(int, input().split())
    ds = {}

    for i in range(N):
        dsMakeSet(ds, i+1)

    n = 0
    for i in range(M):
        X,Y,Z = map(int, input().split())
        if dsUnion(ds, X, Y):
            n += 1
        
    print(N - n)
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    while ds[x] != x:
        x = ds[x]

    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False


def main():
    N, M = map(int, input().split())
    ds = {}

    for i in range(N):
        dsMakeSet(ds, i+1)

    for i in range(M):
        X,Y,Z = map(int, input().split())
        dsUnion(ds, X, Y)
        
    print(len(set(dsFind(ds, x) for x in ds)))
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
cost = N
group = []

for i in range(M):
    x, y, _ = map(int, input().split())
    setxy = set([x, y])

    joinflag = False
    xy_in_group = False
    for si, setg in enumerate(group):
        setgxy = setg & setxy

        if len(setgxy) == 1:
            xy_in_group = True
            if joinflag:
                group[si] = setg | group[ptr]
                del group[ptr]
                break
            else:
                cost -= 1
                group[si] = setg | setxy
                ptr = si
                joinflag = True

        elif len(setgxy) == 2:
            xy_in_group = True
            break

    if not xy_in_group:
        cost -= 1
        group.append(setxy)

print(cost)

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
X, Y = [None]*M, [None]*M
for i in range(M):
    X[i], Y[i], _ = map(int, input().split())

cost = N
group = []

for xyi in range(M):
    setxy = set([X[xyi], Y[xyi]])

    joinflag = False
    xy_in_group = False
    for si, setg in enumerate(group):
        setgxy = setg & setxy

        if len(setgxy) == 1:
            xy_in_group = True
            if joinflag:
                group[si] = setg | group[ptr]
                del group[ptr]
                break
            else:
                cost -= 1
                group[si] = setg | setxy
                ptr = si
                joinflag = True

        elif len(setgxy) == 2:
            xy_in_group = True
            break

    if not xy_in_group:
        cost -= 1
        group.append(setxy)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
X, Y = [None]*M, [None]*M
for i in range(M):
    X[i], Y[i], _ = map(int, input().split())

cost = N
group = []

for xyi in range(M):
    setxy = set([X[xyi], Y[xyi]])

    joinflag = False
    xy_in_group = False
    for si, setg in enumerate(group):
        setgxy = setg & setxy

        if len(setgxy) == 1:
            xy_in_group = True
            if joinflag:
                group[si] = setg | group[ptr]
                del group[ptr]
                break
            else:
                cost -= 1
                group[si] = setg | setxy
                ptr = si
                joinflag = True

        elif len(setgxy) == 2:
            xy_in_group = True
            break

    if not xy_in_group:
        cost -= 1
        group.append(setxy)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, M = map(int,inputs().split())
K = [None]*M
for t in range(M):
	x, y, z = map(int,inputs().split())
	K[t] = (x, y)
c = 0

U = [0]*(N+1)

for k in K:
	if U[k[0]] and U[k[1]]:
		a = U[k[0]]
		while(U[a] != a ):
			a = U[a]
		U[k[1]] = a
	elif U[k[1]]:
		U[k[0]] = U[k[1]]
	elif U[k[0]]:
		U[k[1]] = U[k[0]]
	else:
		U[k[0]] = k[0]
		U[k[1]] = k[0]

ans = 0
group = set()
for u in U[1:]:
	if u == 0:
		ans += 1
		continue
	elif u in group:
		group.add(u)
		continue
	elif u == U[u]:
		ans += 1
		group.add(u)
	else:
		while(u != U[u]):
			group.add(u)
		ans += 1
		group.add(u)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, M = map(int,inputs().split())
K = [None]*M
for t in range(M):
	x, y, z = map(int,inputs().split())
	K[t] = {x, y}
for p in range(M):
	for q in range(M - p -1):
		if K[q].isdisjoint(K[M - p - 1]) == False:
			K[q] = K[q] | K[M - p -1]
			K[M - p -1] = {0}
			continue
c = 0
for p in range(M):
	c += len(K[p]) - 1
print(N - c)

Submission status: Time Limit Exceeded

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

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

# 魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0
index = 0
for x, y, _ in xyz:
    x = x-1
    y = y-1
    if known[x] and known[y]:
        continue;

    # zは気にしなくてよい
    if known[x]:
        if known[y] is False:
            known[y] = True
            judge += 1
    else:
        if known[y]:
            known[x] = True
            judge += 1
        else:
            known[x] = True
            known[y] = True
            judge += 2
            magic_act_num += 1
    i = 0
    for a, b, _ in xyz:
        i+=1
        if i-1 <= index:
            continue
        a = a - 1
        b = b - 1
        if known[a] is x and known[b] is y:
            continue
        if known[a] is y and known[b] is x:
            continue
        if known[a] is x:
            if known[b] is not y:
                known[b] = True
        if known[a] is y:
            if known[b] is not x:
                known[b] = True
        if known[b] is x:
            if known[a] is not y:
                known[a] = True
        if known[b] is y:
            if known[a] is not x:
                known[a] = True
    index+=1

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Time Limit Exceeded

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

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

# 魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0
index = 0
for x, y, _ in xyz:
    x = x-1
    y = y-1
    if known[x] and known[y]:
        continue;

    # zは気にしなくてよい
    if known[x]:
        if known[y] is False:
            known[y] = True
            judge += 1
    else:
        if known[y]:
            known[x] = True
            judge += 1
        else:
            known[x] = True
            known[y] = True
            judge += 2
            magic_act_num += 1
    i = 0
    for a, b, _ in xyz:
        if i <= index:
            continue
        a = a - 1
        b = b - 1
        if known[a] is x and known[b] is y:
            continue
        if known[a] is y and known[b] is x:
            continue
        if known[a] is x:
            if known[b] is not y:
                known[b] = True
        if known[a] is y:
            if known[b] is not x:
                known[b] = True
        if known[b] is x:
            if known[a] is not y:
                known[a] = True
        if known[b] is y:
            if known[a] is not x:
                known[a] = True
        i+=1
    index+=1

magic_act_num += (N-judge)

print(magic_act_num)