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: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):    #xの根を返す
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    #親の更新(根を直接親にして参照距離を短く)
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    #xとyを繋げる
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

N,M = inpl()

table = [i for i in range(N)]    #木の親 table[x] == x なら根
rank  = [1 for i in range(N)]    #木の長さ
size  = [1 for i in range(N)]    #集合のサイズ

for i in range(M):
    x,y,z = inpl()
    x -= 1
    y -= 1
    Unite(x,y)

print(len(set(table)))

Submission status: Wrong Answer

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

def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(M):
        conn[X[i] - 1].append(Y[i] - 1)
        conn[X[i] - 1].append(Y[i] - 1)

    def dfs(idx, conn, visited):
        visited[idx] = True
        for c in conn[idx]:
            if not visited[c]:
                dfs(c, conn, visited)
        return visited

    visited = [False] * N
    ret = 0
    for i in range(N):
        if not visited[i]:
            visited = dfs(i, conn, visited)
            ret += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]" 
    Y = [int()] * (M)  # type: "List[int]" 
    Z = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


parent = [i for i in range(N)]
rank = [0] * N


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


for i in range(M):
    X, Y, Z = map(int, input().split())
    X, Y = X - 1, Y - 1
    unite(X, Y)

D = {}
num = 0
for i in range(N):
    if parent[i] not in D:
        D[parent[i]] = 1
        num += 1

print(num)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    s = input()
    for i in range(k-1):
        print(s[i],end = "")
    print(s[k-1].lower(),end = "")
    for i in range(k,n):
        print(s[i],end = "")
    print()
    return

#B
def B():
    s = S()
    k = int(s[0])*10+int(s[1])
    l = int(s[2])*10+int(s[3])
    if k == 0:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")
    elif k < 13:
        if l == 0:
            print("MMYY")
        elif l < 13:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    else:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")

#C
def C():
    n,k = LI()
    ans = 0
    for i in range(1,n+1):
        l = k/i
        ans += 1/n*1/(2 << max(0,math.ceil(math.log(l,2))))
    print(ans*2)
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y,w = LI()
        x -= 1
        y -= 1
        v[x].append((y,w))
        v[y].append((x,w))
    ans = [0 for i in range(n)]
    bfs_map = [1 for i in range(n)]
    bfs_map[0] = 0
    q = deque()
    q.append(0)
    while q:
        x = q.popleft()
        for y,w in v[x]:
            if bfs_map[y]:
                if w%2:
                    ans[y] = ans[x]^1
                else:
                    ans[y] = ans[x]
                bfs_map[y] = 0
                q.append(y)
    for i in ans:
        print(i)
    return

#E
def E():
    def root(x):
        if par[x] == x:
            return par[x]
        par[x] = root(par[x])
        return par[x]
    def same(x,y):
        return root(x) == root(y)
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    for i in range(m):
        x,y,z = LI()
        x -= 1
        y -= 1
        if not same(x,y):
            unite(x,y)
    par = list(set(par))
    print(len(par))
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Time Limit Exceeded

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

N, M = map(int,input().split())
adj = [[] for i in range(N+1)]
for i in range(M):
	u, v, w = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)

vis = [False for i in range(N+1)]
def dfs(u):
	if vis[u]:
		return
	vis[u] = True
	for v in adj[u]:
		dfs(v)

ans = 0
for u in range(1,N+1):
	if not vis[u]:
		ans += 1
		dfs(u)

print(ans)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親ならグループの人数のマイナス倍を、そうでないなら（元）親の番号を示す

def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        
        return r(root[x])

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    
    root[x]+=root[y]
    root[y]=x

for i in range(m):
    x,y,z=map(int,input().split())
    unite(x,y)


g=[0]*(n+1)
for i in range(1,n+1):
    g[r(i)]+=1
ans=0
for i in range(n+1):
    if g[i]>0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = [int(x) for x in input().split()]
data = [[0]*n for _ in range(m)]
for i in range(m):
    x, y, _ = [int(x) - 1 for x in input().split()]
    data[i][x], data[i][y] = 1, -1

mat = np.array(data)
r = np.linalg.matrix_rank(mat)

ans = n - r

print(ans)

Submission status: Time Limit Exceeded

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

card = [[] for _ in range(n)]

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

checked = [False] * n

count = 0
from collections import deque
for i in range(n):
    if checked[i]:
        continue
    count += 1
    q = deque([i])
    while q:
        j = q.popleft()
        checked[j] = True
        for k in card[j]:
            if not checked[k]:
                q.append(k)
print (count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=list(map(int,input().split()))
even_list=[list(map(int,input().split())) for _ in range(M)]
#リストVのN番目には頂点Nがあり、そこには頂点Nとつながっている頂点が入っている。
    
#seen[i]は、頂点iを訪問済みの場合はTrue、未訪問の場合はFalse
seen=[False for i in range(N+1)]


count=0
graph=[[] for _ in range(N+1)]
for i in even_list:
    graph[i[0]].append(i[1])
    graph[i[1]].append(i[0])

def StackBFS(s):
    #graphのN番目には頂点Nがあり、そこには頂点Nとつながっている頂点が入っている。
    S=deque([s])
    C=set()
    
    while S:
        v=S.popleft()
        seen[v]=True #訪問済みの頂点をTrueにする
        if v not in C:
            C=C|{v}
            for i in graph[v]:
                S.append(i)

for i in range(1,N+1):
    if seen[i]==False:
        StackBFS(i)
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=list(map(int,input().split()))
even_list=[list(map(int,input().split())) for _ in range(M)]
#リストVのN番目には頂点Nがあり、そこには頂点Nとつながっている頂点が入っている。
    
#seen[i]は、頂点iを訪問済みの場合はTrue、未訪問の場合はFalse
seen=[False for i in range(N+1)]


count=0
graph=[[] for _ in range(N+1)]
for i in even_list:
    graph[i[0]].append(i[1])
    graph[i[1]].append(i[0])

def StackBFS(s):
    #graphのN番目には頂点Nがあり、そこには頂点Nとつながっている頂点が入っている。
    S=deque([s])
    C=set()
    
    while S:
        v=S.pop()
        seen[v]=True #訪問済みの頂点をTrueにする
        if v not in C:
            C=C|{v}
            for i in graph[v]:
                S.append(i)

for i in range(1,N+1):
    if seen[i]==False:
        StackBFS(i)
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(v):
  if len(edge[v])==0:
    return 0
  for u in edge[v]:
    if visited[u]==False:
      visited[u]=True
      dfs(u)
  return 0

ans = 0
visited = [False]*N
for i in range(N):
  if visited[i]==False:
    visited[i]=True
    dfs(i)
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,M = I()
links = [[] for _ in range(N)]
for i in range(M):
    x,y,z = I()
    links[x-1].append(y-1)
    links[y-1].append(x-1)
ans = 0
visited = [0]*N
def dfs(n):
    if visited[n]:
        return
    visited[n] = 1
    for l in links[n]:
        dfs(l)
for i in range(N):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(v) for v in input().split()]
hints = [None for _ in range(0, n)]

for i in range(0, m):
    x, y, z = [int(v) for v in input().split()]

    hx = hints[x - 1]
    hy = hints[y - 1]

    if hx is None and hy is None:
        hints[x - 1] = min([x, y])
        hints[y - 1] = min([x, y])
    elif hx is None:
        hints[x - 1] = hy
    elif hy is None:
        hints[y - 1] = hx
    else:
        hints = [h if h != hy else hx for h in hints]

count = hints.count(None)
count += len(set([h for h in hints if h is not None]))
print(count)

Submission status: Time Limit Exceeded

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

for _i in range(m):
    x, y, z = map(int, input().split())
    while tree[x]>0:
        x = tree[x]
    while tree[y]>0:
        y = tree[y]
    if x==y:
        continue
    else:
        tree[x] = y
print(sum(1 for i in tree if i<0))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    def dfs(v):
        for u in tree[v]:
            if visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u)

    visited = [False for _ in range(n)]
    res = 0
    for i in range(n):
        if not visited[i]:
            res += 1
            visited[i] = True
            dfs(i)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,defaultdict

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

G = defaultdict(list)
for i in range(M):
    G[data[i][0]].append(data[i][1])
    G[data[i][1]].append(data[i][0])

D = [0]+[-1]*(N)

c = 0
for i in range(1,N+1):
    if D[i] != -1:
        continue
    else:
        q = deque([i])
        while q:
            n = q.pop()
            D[n] = 0
            for d in G[n]:
                if D[d] != -1:
                    continue
                else:
                    q.append(d)
        c += 1

print(c)

Submission status: Time Limit Exceeded

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        temp=set([i])
        no_checked[i-1]=1
        while len(list(temp))>0:
            v=temp.pop()
            for item in xyz[v]:
                if no_checked[item-1]==0:
                    no_checked[item-1]=1
                    temp.add(item)
                    xyz[item].remove(v)
    #print(i,no_checked)
print(cnt)

Submission status: Time Limit Exceeded

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=set([i for i in range(1,n+1)])

cnt=0
while no_checked != set([]):
    cnt+=1
    i=no_checked.pop()
    temp=set([i])
    while len(list(temp))>0:
        v=temp.pop()
        for item in xyz[v]:
            if item in no_checked:
                no_checked.remove(item)
                temp.add(item)
                xyz[item].remove(v)

print(cnt)

Submission status: Time Limit Exceeded

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

checked=set([i for i in range(1,n+1)])

cnt=0
while checked != set([]):
    cnt+=1
    i=checked.pop()
    temp=set([i])
    while len(list(temp))>0:
        v=temp.pop()
        for item in xyz[v]:
            if item in checked:
                checked.remove(item)
                temp.add(item)
                xyz[item].remove(v)

print(cnt)

Submission status: Time Limit Exceeded

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

checked=set([])

cnt=0
for i in range(1,n+1):
    if i not in checked:
        cnt+=1
        temp=set([])
        temp.add(i)
        checked.add(i)
        while len(list(temp))>0:
            v=temp.pop()
            for item in xyz[v]:
                if item not in checked:
                    checked.add(item)
                    temp.add(item)
                    xyz[item].remove(v)
    #print(i,checked)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
a = []
x,y,_ = map(int, input().split())
a.append([x,y])

for _ in range(M-1):
    X,Y,_ = map(int, input().split())
    s = 0
    for sub in a:
        if not set([X,Y]).isdisjoint(set(sub)):
            sub.extend([X,Y])
            break

        else:
            s += 1
            if s == len(a):
                a.append([X,Y])

c = 0        
for i in a:
    c += len(set(i))
    
print(len(a) + N - c)

Submission status: Time Limit Exceeded

Solution code:
import copy
N,M = map(int,(input().split()))
x = [0]*M
y = [0]*M
z = [0]*M
line = [[] for _ in range(N+1)]
dot = []
for i in range(M):
    x[i],y[i],z[i] = map(int,(input().split()))
    line[x[i]].append(y[i])
    line[y[i]].append(x[i])
    dot.append(x[i])
    dot.append(y[i])

f = [0]*N
nohint = 0
hint = [0]*(N+1)
for i in range(1,N+1):
    f[i-1] = dot.count(i)
    if f[i-1] == 0:
        nohint += 1
    else:
        hint[i] = 1

not_visit = [False]*(N+1)
for i in range(len(hint)):
    if hint[i] == 1:
        not_visit[i] = True

ans = 0
stack = []
while sum(hint):
    stack.append(hint.index(1))
    while stack:
        now = stack.pop()
        if not_visit[now]:
            hint[now] = 0
            for i in line[now]:
                stack.append(i)
                hint[i] = 0
        not_visit[now] = False
    ans += 1
print(ans + nohint)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def search():
  visited = [False] * len(g)
  ans = 0 
  
  while not all(visited):
    s0 = visited.index(False)
    visited[s0] = True
    q = deque([s0+1])
    ans += 1
    while q:
      s = q.popleft()
      for t in g[s]:
        if not visited[t-1]:
          q.append(t)
          visited[t-1] = True
  return ans

N,M = map(int,input().split())
g = {i+1: [] for i in range(N)}
for i in range(M):
    x,y,z = map(int,input().split())
    g[x].append(y)
    g[y].append(x)
print(search())

Submission status: Time Limit Exceeded

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

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

G = [[] for _ in range(N + 1)]
for el in XYZ:
    x, y, z = el
    G[x].append(y)
    G[y].append(x)

seen=[False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)

cnt = 0
for start in range(1, N + 1):
    if seen[start] == False:
        dfs(start)
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
b = [[int(i) for i in input().split(" ")] for j in range(m)]
b = sorted(b)
used = [0]*n
a = [[] for i in range(n)]
check = []

for i in b:
    a[i[0]-1].append(i[1]-1)
    a[i[1]-1].append(i[0]-1)
    check.extend([i[0]-1, i[1]-1])

check = set(check)
c = 0
for i in check:
    if used[i] == 1:
        continue
    
    c += 1
    ch_ = [i] + a[i]
    ind = 1
    while True:
        if ind == len(ch_):
            break
        temp = a[ch_[ind]]
        for j in temp:
            if not j in ch_:
                ch_.append(j)
        ind += 1
    for j in ch_:
        used[j] = True
print(n-len(check)+c)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
b = [[int(i) for i in input().split(" ")] for j in range(m)]
lis = [b[0][:-1]]
for i in range(1, m):
    tm = b[i][:-1]
    flag = 0
    temp = [j for j in range(len(lis)) if tm[0] in lis[j] or tm[1] in lis[j]]
    if temp == []:
        lis.append(tm)
    else:
        for j in range(1, len(temp)):
            lis[temp[0]] += lis[temp[j]-j+1]
            lis.pop(temp[j]-j+1)   
        if not tm[0] in lis[temp[0]]:
            lis[temp[0]].append(tm[0])
        if not tm[1] in lis[temp[0]]:
            lis[temp[0]].append(tm[1])
            
c = n - sum([len(k) for k in lis])
print(len(lis) + c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
E = [[] for _ in range(N+1)]
for i in range(M):
    x,y,z = map(int,input().split())
    E[x].append(y)
    E[y].append(x)

d = [-1]*(N+1)

def dfs(start,num):
    q = deque([start])
    while(q):
        v = q.pop()
        if(d[v] == -1):
            d[v] = num
        for s in E[v]:
            if(d[s] == -1):
                q.append(s)

group_num = 0
for i in range(1,N+1):
    if(d[i] == -1):
        group_num += 1
        dfs(i,group_num)

print(group_num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
E = [[] for _ in range(N+1)]
for i in range(M):
    x,y,z = map(int,input().split())
    E[x].append(y)
    E[y].append(x)

d = [-1]*(N+1)

def dfs(start,num):
    q = deque([start])
    while(q):
        v = q.pop()
        if(d[v] == -1):
            d[v] = num
        for s in E[v]:
            if(d[s] == -1):
                q.append(s)

group_num = 0
for i in range(1,N+1):
    if(d[i] == -1):
        group_num += 1
        dfs(i,group_num)

print(group_num)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
b = [[int(i) for i in input().split(" ")] for j in range(m)]
used = [False for i in range(n)]
c = 0
a = [[0 for i in range(n)] for i in range(n)]
for i in b:
    a[i[0]-1][i[1]-1] = 1
    a[i[1]-1][i[0]-1] = 1

for i in range(n):
    if used[i] == True:
        continue
    c += 1
    
    check = [i]
    if 1 in a[i]:
        check += [j for j in range(n) if a[i][j]==1]
    ind = 1
    while True:
        if ind == len(check):
            break
        temp = a[check[ind]]
        if 1 in temp:
            tm = [j for j in range(n) if temp[j]==1]
            for j in tm:
                if j in check:
                    continue
                check.append(j)
        ind += 1
    for j in check:
        used[j] = True
print(c)

Submission status: Time Limit Exceeded

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

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

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

seen=[False]*(N+1)
todo=queue.Queue()
def dfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        dfs(check)
print(cnt)

Submission status: Time Limit Exceeded

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

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

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

tosee = set()
for i in range(1,N+1):
    tosee.add(i)
#print(tosee)
todo=queue.Queue()
def dfs(n):
    if n in tosee:
        tosee.remove(n)
    for nxt in G[n]:
        if nxt in tosee:
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())


cnt=0
while tosee:
    cnt+=1
    dfs(tosee.pop())
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N+1)]
    
    for _ in range(M):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        G[x].append(y)
        G[y].append(x)
    
    seen = [False]*(N)
    ans = 0
    def dfs(v):
        if seen[v]:
            return
        seen[v] = True
        for nv in G[v]:
            dfs(nv)
    
    for v in range(N):
        if not seen[v]:
            dfs(v)
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N,M = map(int,input().split())
G = [[] for _ in range(N+1)]

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

seen = [False]*(N)
ans = 0
def dfs(v):
    if seen[v]:
        return
    seen[v] = True
    for nv in G[v]:
        dfs(nv)

for v in range(N):
    if not seen[v]:
        dfs(v)
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
G = [[] for _ in range(N)]

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

seen = [False]*(N)
ans = 0
def dfs(v):
    if seen[v]:
        return
    seen[v] = True
    for nv in G[v]:
        dfs(nv)

for v in range(N):
    if not seen[v]:
        dfs(v)
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ans = [-1] * N

def find(x):
    global ans
    if ans[x] == -1:
        return x
    else:
        return find(ans[x])
    
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    xx = find(x)
    yy = find(y)
    if ans[x] == ans[y] == -1:
        ans[y] = x
    elif xx == yy:
        continue
    else:
        ans[yy] = xx

n = 0
for i in ans:
    if i == -1:
        n += 1

print(n)

Submission status: Time Limit Exceeded

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


class Node:
    def __init__(self, index):
        self.index = index
        self.ref = []
        self.visited = False

    def append(self, node):
        self.ref.append(node)
        node.ref.append(self)

    def visit(self):
        self.visited = True
        for r in self.ref:
            if not r.visited:
                r.visit()


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    nodes = [Node(i) for i in range(N)]
    X = [x-1 for x in X]
    Y = [y-1 for y in Y]
    for i in range(M):
        nodes[X[i]].append(nodes[Y[i]])
    sum = 0
    for i in range(N):
        if not nodes[i].visited:
            sum += 1
            nodes[i].visit()
    print(sum)
    return


# Generated by 1.1.6 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:
N, M = map(int, input().split())

re = [1]*N
ans = [1]*N
for k in range(N):
  ans[k] = k
 
A = 0
 
for i in range(M):
  X, Y, Z = map(int, input().split())
  if ans[X-1] != ans[Y-1]:
    if re[X-1] == 0 :
      ans = [ans[X-1] if i == ans[Y-1] else i for i in ans]
      re[Y-1] = 0
    elif re[Y-1] == 0:
      ans = [ans[Y-1] if i == ans[X-1] else i for i in ans]
      re[X-1] = 0
    else:
      ans[X-1] = ans[Y-1]
      re[X-1] = 0
      re[Y-1] = 0


    A = A+1
 
print(N-A)
#print(ans)

Submission status: Time Limit Exceeded

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

def main():
    n, m = [int(i) for i in input().split()]
    adj = lil_matrix((n, n), dtype=int)
    for _ in range(m):
        x, y, z = [int(i) for i in input().split()]
        adj[x-1, y-1] = 1
    print(connected_components(adj)[0])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class UnionFind():
  def __init__(self,n):
    self.parent={}
    for i in range(n):
      self.parent[i]=[i]
      
  def find_parent(self,x):
    import sys
    parent=self.parent
    for key in parent.keys():
      if x in parent[key]:
        return key
        sys.exit()
        
  def union(self,x,y):
    parent=self.parent
    x_par,y_par=self.find_parent(x),self.find_parent(y)
    if x_par==y_par:
      pass
    else:
      if len(parent[x_par])<len(parent[y_par]):
        parent[y_par]+=parent[x_par]
        parent.pop(x_par)
      else:
        parent[x_par]+=parent[y_par]
        parent.pop(y_par)
    self.parent=parent
    return None
  
  def same(self,x,y):
    if self.find_parent(x)==self.find_parent(y):
      return True
    else:
      return False
  def cnt(self):
    par=self.parent
    return len(set(par))
uf=UnionFind(N)
for i in range(M):
  x,y,z=map(int,input().split())
  uf.union(x-1,y-1)
print(uf.cnt())

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 sum(visited) == N:
        ans = i
        break
print(ans)

Submission status: Time Limit Exceeded

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

def dfs(s):
    if visited[s]:
        return
    visited[s] = 1
    for to in t[s]:
        if visited[to]:
            continue
        dfs(to)
    
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, N + 1):
    s = visited.index(0)
    dfs(s)
    if min(visited):
        ans = i
        break
print(ans)