Problem:


Score : 500 points

Problem Statement

There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.

Let A_i be the integer written on the i-th card.

Your objective is to guess A_1, A_2, ..., A_N correctly.

You know the following facts:

For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.

You are a magician and can use the following magic any number of times:

Magic: Choose one card and know the integer A_i written on it. The cost of using this magic is 1.

What is the minimum cost required to determine all of A_1, A_2, ..., A_N?

It is guaranteed that there is no contradiction in given input.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq X_i < Y_i \leq N

1 \leq Z_i \leq 100

The pairs (X_i, Y_i) are distinct.

There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)

Input

Input is given from Standard Input in the following format:

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M

Output

Print the minimum total cost required to determine all of A_1, A_2, ..., A_N.

Sample Input 1

3 1
1 2 1

Sample Output 1

2

You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.

Sample Input 2

6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5

Sample Output 2

2

Sample Input 3

100000 1
1 100000 100

Sample Output 3

99999



Sample input:
3 1
1 2 1


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
N, M = (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

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

    for a, b, _ in xyz:
        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

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        #木の高さを格納する
        self.rank=[0]*(n+1)
        
    def find(self,x):
        if self.par[x]==x:#根ならその番号を返す
            return x
        else:#根じゃないなら親を指定して再検索
            self.par[x]=self.find(self.par[x])
            return self.find(self.par[x])
    def same_chk(self,x,y):#x,yが同じグループに所属するか確認
        return self.find(x)==self.find(y)
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

n,m=map(int, input().split())
xyz=[]
for i in range(m):
    xyz.append(list(map(int, input().split())))
#n,m=6,5
#xyz=[[1,2,1],[2,3,2],[1,3,3],[4,5,4],[5,6,5]]
uf=UnionFind(n)
for i in range(m):
    uf.union(xyz[i][0],xyz[i][1])
root=[]
for i in range(1,n+1):
    temp_root0=uf.find(i)
    if temp_root0 not in root:
        root.append(temp_root0)
    temp_root1=uf.find(i)
    if temp_root1 not in root:
        root.append(temp_root1)
print(len(root))

Submission status: Time Limit Exceeded

Solution code:
def search(n):
    while A[n-1] != n:
        n = A[n-1]

    return n

N, M = list(map(int, input().split()))
A = [i for i in range(1, N+1)]
ans = 0

for i in range(M):
    X, Y, Z = list(map(int, input().split()))
    X_root, Y_root = search(X), search(Y)

    if X_root != Y_root:
        A[X_root-1] = Y_root
        ans += 1

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
class Union:
    def __init__(self, n):
        self.root = True
        self.parent = n
        self.size = 1

    def update(self, n, size):
        self.root = False
        self.parent = n
        self.size += size

def search(n):
    global A

    while not A[n-1].root:
        n = A[n-1].parent

    return n, A[n-1].size

N, M = list(map(int, input().split()))
A = [Union(i) for i in range(1, N+1)]
ans = 0

for i in range(M):
    X, Y, Z = list(map(int, input().split()))
    X_root, X_size = search(X)
    Y_root, Y_size = search(Y)

    if X_root != Y_root:
        if X_size < Y_size:
            a, b, size = X_root, Y_root, Y_size
        else:
            a, b, size = Y_root, X_root, X_size

        A[a-1].update(b, size)
        ans += 1

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
class Union:
    def __init__(self, n):
        self.root = True
        self.parent = n

    def update(self, n):
        self.root = False
        self.parent = n

def search(n):
    global A

    while not A[n-1].root:
        n = A[n-1].parent

    return n

N, M = list(map(int, input().split()))
A = [Union(i) for i in range(1, N+1)]
nums = [i for i in range(1, N+1)]

for i in range(M):
    X, Y, Z = list(map(int, input().split()))
    X_root = search(X)
    Y_root = search(Y)

    if X_root != Y_root:
        A[Y_root-1].update(X_root)
        nums.remove(Y_root)

print(len(nums))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]  # 親
		self.rank = [1] * n  # 深さ
		self.size = [1] * n  # size[i]はiを根とするグループのサイズ

	def find(self, x):  # xの親を返す
		if self.par[x] == x:
			return x
		else:
			return self.find(self.par[x])

	def unite(self, x, y):  # x,yの属する集合をマージする
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[x] = y
				self.size[y] += self.size[x]
			else:
				self.par[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

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())

uf = UnionFind(N)

for j in range(M):
	uf.unite(X[j] - 1, Y[j] - 1)

ans = 0
root = []
for k in range(N):
	tmp = uf.find(k)
	if tmp not in root:
		ans += 1
		root.append(tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]  # 親
		self.rank = [1] * n  # 深さ
		self.size = [1] * n  # size[i]はiを根とするグループのサイズ

	def find(self, x):  # xの親を返す
		if self.par[x] == x:
			return x
		else:
			return self.find(self.par[x])

	def unite(self, x, y):  # x,yの属する集合をマージする
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[x] = y
				self.size[y] += self.size[x]
			else:
				self.par[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

	def same(self, x, y):  # x,yが同じ集合に属するか判定する
		return self.find(x) == self.find(y)

	def group_size(self, x):  # xが属する集合の大きさを返す
		return self.size[self.find(x)]

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())

uf = UnionFind(N)

for j in range(M):
	uf.unite(X[j] - 1, Y[j] - 1)

ans = 0
root = []
for k in range(N):
	tmp = uf.find(k)
	if tmp not in root:
		ans += 1
		root.append(tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

    edge[x-1].append(y-1)
    edge[y-1].append(x-1)

check = [False] * N

q = deque([0])
count = 1 # 連結成分の数

while True:
    while q :
        current = q.popleft()

        if not check[current] :
            check[current] = True

            for n in edge[current] :
                if not check[n] :
                    q.append(n)

    for v , status in enumerate(check) :
        if(not status) :
            q = deque([v])
            count += 1
            break
    else :
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

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

cost = 0
for i in range(N):
	if c[i] == 0:
		cost += 1
		q.append(i)
		for _ in range(N):
			if len(q) == 0:
				break
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

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

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		for _ in range(N):
			if len(q) == 0:
				break
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

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

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		while len(q):
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

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

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		while len(q):
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

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

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		while len(q):
			j = q.pop(0)
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0 for i in range(N)]
A = [[] for i in range(N)]

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

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		while len(q):
			j = q.pop(0)
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)

Submission status: Time Limit Exceeded

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

xy = [0 for _ in range(n + 1)]


def root(x):
    i = x
    while xy[i] != 0:
        i = xy[i]
    return i


for _ in range(m):
    x, y, z = map(int, input().split())
    rx = root(x)
    ry = root(y)
    if rx != ry:
        xy[ry] = rx

ans = 0
for i in xy[1:]:
    if i == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

clusters = []
nums = defaultdict(int)
for i in range(M):
  x, y, z = map(int, input().split())
  clusters.append(set([x, y]))
  nums[x] += 1
  nums[y] += 1

for i in nums:
  new_clusters = []
  if nums[i] < 2:
    continue
  merged_cluster = set()
  for cluster in clusters:
    if i in cluster:
      merged_cluster = merged_cluster | cluster
    else:
      new_clusters.append(cluster)
  new_clusters.append(merged_cluster)
  clusters = list(new_clusters)

num_not_in_clusters = N - len(nums)
print(len(clusters) + num_not_in_clusters)

Submission status: Time Limit Exceeded

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

s = set(sum(xy, []))

for a in xy:
    for b in xy:
        if not a == b:
            for c in b:
                if c in a:
                    a += b
                    xy.remove(b)
                    break

print(n - len(s) + len(xy))

Submission status: Time Limit Exceeded

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

par = [i for i in range(n+1)]
rank = [0] * (n+1)

def find(x):
  if par[x] == x:
    return x
  return find(par[x])

def unite(x,y):
  root_x = find(x)
  root_y = find(y)
  if rank[root_x] != rank[root_y]:
    par[min(root_x,root_y)] = max(root_x,root_y)
  else:
    par[root_y] = root_x
    rank[root_x] += 1


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

for i in range(n):
  roo.append(find(i+1))

print(len(set(roo))-1)

Submission status: Time Limit Exceeded

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

lst = list(range(1, N+1))
cnt = 0
for i in range(M):
    x, y, z = map(int, input().split())
    if lst[x-1] > 0 and lst[y-1] > 0:
        cnt -= 1
        lst[x-1] = cnt
        lst[y-1] = cnt
    elif lst[x-1] < 0 and lst[y-1] < 0:
        lst = [lst[x-1] if i == lst[y-1] else i for i in lst]
    else:
        cluster = min(lst[x-1], lst[y-1])
        lst[x-1] = cluster
        lst[y-1] = cluster

print(len(set(lst)))

Submission status: Time Limit Exceeded

Solution code:

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

isles = []

for i in range(M):
    x, y, z = map(int, input().split())
    x_k = None
    y_k = None
    for k, l in enumerate(isles):
        if x in l:
            x_k = k
        if y in l:
            y_k = k
    if x_k is None and y_k is None:
        isles.append([x, y])
    elif x_k is None:
        isles[y_k].append(x)
    elif y_k is None:
        isles[x_k].append(y)
    else:
        if x_k != y_k:
            isles[x_k] += isles[y_k]
            del isles[y_k]
#     print(isles)

# isles = [[1, 2, 3], [4, 5, 6]]
# N = 6

# isles = [[1, 2]]
# N = 3

# print(isles)
c = len(isles) + (N-sum([len(x) for x in isles]))

print(c)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [0]*N
input_num = []
count = 0
for _ in range(M):
    X, Y, _ = map(int, input().split())
    input_num.append((X, Y))
while input_num:
    flag = True
    while flag:
        flag = False
        for index, (X, Y) in enumerate(input_num):
            if A[X-1] == 1 or A[Y-1] == 1:
                A[X-1], A[Y-1] = 1, 1
                input_num.pop(index)
                flag = True
    if input_num:
        x, y = input_num.pop()
        A[x-1] = 1
        A[y-1] = 1
        count += 1
for a in A:
    if a == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, M = map(int, input().split())
A = [0]*N
input_num = []
count = 0
zero_lis = []
for _ in range(M):
    X, Y, _ = map(int, input().split())
    input_num.append((X, Y))
while input_num:
    flag = True
    while flag:
        flag = False
        for index, (X, Y) in enumerate(input_num):
            if A[X-1] == 1 or A[Y-1] == 1:
                A[X-1], A[Y-1] = 1, 1
                input_num.pop(index)
                flag = True
            else:
                zero_lis.append(X-1)
                zero_lis.append(Y-1)
    if zero_lis:
        for num, _ in Counter(zero_lis).most_common():
            if A[num] != 1:
                A[num] = 1
                count += 1
                zero_lis.clear()
                break
for a in A:
    if a == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self, val):
        self.num = val
        self.val = val
        self.is_parent = True
        self.parent = None
        self.childs = []

    def show(self):
        print(self.num, end=" ")
        print(self.is_parent, end=" ")
        for child in self.childs:
            print(child.num, end=" ")

def root(node):
    while node.parent != None:
        node = node.parent
    return node

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

roots = [Node(i) for i in range(N)]
count = N

for i in range(M):
    x, y, z = map(int, input().split())
    x = roots[x-1]
    y = roots[y-1]
    if x.is_parent and y.is_parent:
            y.is_parent = False
            y.parent = x
            count -= 1
            x.childs.append(y)
    else:
        root_x = root(x)
        root_y = root(y)
        if root_x != root_y:
            root_y.is_parent = False
            root_y.parent = root_x
            count -= 1
            root_x.childs.append(root_y)

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
xyz = [[] for i in range(n+1)]
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append(y)
    xyz[y].append(x)
    
ans = 0
visited = [False]*(n+1)
for x in range(1, n+1):
    if visited[x]:
        continue

    que = deque(xyz[x])
    while len(que) > 0:
        y = que.popleft()
        visited[y] = True
        for yn in xyz[y]:
            if not visited[yn]:
                que.append(yn)
    ans += 1
    
# print(visited)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100010)

N, M = map(int,input().split())
E = [[] for k in range(N)]

for k in range(M):
    X, Y, Z = map(int,input().split())
    E[X-1].append(Y-1)
    E[Y-1].append(X-1)
G = [-1]*N

def dfs(now,group):
    if G[now] == -1:
        G[now] = group
        for tsugi in E[now]:
            dfs(tsugi,group)

ans = 0
for k in range(N):
    if G[k] == -1:
        dfs(k,ans)
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
xyz = {i:[] for i in range(1, n+1)}
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append((x, y, z))
    xyz[y].append((y, x, z))

connects = [0]*(n+1)
group = 1
for i in range(1, n+1):
    if connects[i] > 0:
        continue
    if len(xyz[i]) == 0:
        connects[i] = group
        group += 1
        continue

    que = deque(xyz[i])
    connects[i] = group
    while len(que) > 0:
        x, y, z = que.popleft()
        connects[y] = group
        for xn, yn, zn in xyz[y]:
            if connects[yn] > 0:
                pass
            else:
                que.append((xn, yn, zn))
    group += 1
    
# print(connects)
print(max(connects))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

Y = [ [] for _ in range(N)]
for x in X:
    Y[x[0]-1].append((x[0], x[1], x[2]))
    Y[x[1]-1].append((x[1], x[0], x[2]))
# print(Y)

visited = [False] * N
count = 0
que = deque()

for i in range(len(Y)):
    if len(Y[i]) == 0:
        visited[i] = True
        count +=1

while True:
    if not False in visited:
        break
    count += 1
    que.append(visited.index(False))
    
    while len(que)>0:
        v = que.popleft()
        visited[v] = True
        for y in Y[v]:
            if not visited[y[1]-1]:
                que.append(y[1]-1)
    

print(count)

Submission status: Time Limit Exceeded

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


def root(x):
    while nodes[x] != x:
        x = nodes[x]
    return x


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


def unite(x, y):
    if not same(x, y):
        nodes[root(y)] = root(x)


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


ans = 0
for i in range(len(nodes)):
    if nodes[i] == i:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

relation = [[] for _ in range(N+1)]

for _ in range(M) :
	X, Y, Z = map(int, input().split())
	relation[X].append(Y)
	relation[Y].append(X)

visited = [False] * (N + 1)

def dfs(init) :
	queue = [init]

	while queue :
		x_ = queue.pop(0)
		visited[x_] = True

		for y_ in relation[x_] :
			if not visited[y_] :
				queue.append(y_)

# 閉路ごとdfs実行
n_closed = 0
for i in range(1, N + 1) :
	if len(relation[i]) and not visited[i] :
		n_closed += 1
		dfs(i)

print(n_closed + visited.count(False) - 1)

Submission status: Time Limit Exceeded

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

relation = [[] for _ in range(N+1)]

for _ in range(M) :
	X, Y, Z = map(int, input().split())
	Z &= 1
	relation[X].append((Y, Z))
	relation[Y].append((X, Z))

visited = [False] * (N + 1)
p = [-1] * (N + 1)

def dfs(init) :
	queue = [init]
	p[init] = 0

	while queue :
		x_ = queue.pop(0)
		visited[x_] = True

		for y_, z_ in relation[x_] :
			if not visited[y_] :
				p[y_] = (z_ & 1) ^ p[x_]
				queue.append(y_)

# 閉路ごとdfs実行
n_closed = 0
for i in range(1, N + 1) :
	if len(relation[i]) and not visited[i] :
		n_closed += 1
		dfs(i)

print(n_closed + visited.count(False) - 1)

Submission status: Time Limit Exceeded

Solution code:
ans,n=map(int,input().split())
l=[list(map(int,input().split())) for i in range (n)]
a=[i for i in range(ans)]
for i in range (n):
    if a[l[i][0]-1]==a[l[i][1]-1]:
        continue
    else:
        for k in range(2):
            for j in range (n):
                if a[l[i][1]-1]==a[l[j][k]-1]:
                     a[l[j][k]-1]=a[l[i][0]-1]
b=set()
for m in range (ans):
    b.add(a[m])
print(len(b))

Submission status: Time Limit Exceeded

Solution code:
ans,n=map(int,input().split())
l=[list(map(int,input().split())) for i in range (n)]
a=[i for i in range(ans)]
for i in range (n):
    if l[i][0]==l[i][1]:
        continue
    else:
        for k in range(2):
            for j in range (n):
                if a[l[i][1]-1]==a[l[j][k]-1]:
                     a[l[j][k]-1]=a[l[i][0]-1]
b=set()
for m in range (ans):
    b.add(a[m])
print(len(b))

Submission status: Time Limit Exceeded

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

relation = [[] for _ in range(N+1)]

for _ in range(M) :
	X, Y, Z = map(int, input().split())
	Z &= 1
	relation[X].append((Y, Z))
	relation[Y].append((X, Z))

visited = [False] * (N + 1)
p = [-1] * (N + 1)

def dfs(init) :
	queue = [init]
	p[init] = 0

	while queue :
		x_ = queue.pop(0)
		visited[x_] = True

		for y_, z_ in relation[x_] :
			if visited[y_] :
				if (z_ & 1) ^ p[x_] != p[y_] :
					return False
			else :
				p[y_] = (z_ & 1) ^ p[x_]
				queue.append(y_)

	return True

def calc() :
	# 閉路ごと実行
	res = 0
	for i in range(1, N + 1) :
		if len(relation[i]) and not visited[i] :
			res += 1
			if not dfs(i) :
				return -1

	return res + visited.count(False) - 1

print(calc())

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools, random
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right; sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, m = wi()
#XYZ
w = mi(m)

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [-1 for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        """self.rank = [0] * (n + 1)"""


    # 検索
    # 根ならその番号を返す
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

        # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if x != y:
            if self.par[x] < self.par[y]:#par<0の小さい方に合わせる
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
            # 木の高さが同じなら片方を1増やす
                """if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1"""

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]
u = UnionFind(n)
for i in range(m):
    u.union(w[i][0], w[i][1])

se = set()
for i in range(1, n + 1):
    se.add(u.find(i))


print(len(se))

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline

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

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

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

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

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

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