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:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]  # 自身が親だとして初期化
        self.rank = [0 for _ in range(n)]  # 自身が根なので根の深さ0として初期化

    def find(self, x):
        """xの属する根を求める"""
        if self.par[x] == x:  # 親が自分自身なら自分が根
            return x
        else:
            self.par[x] = self.find(self.par[x])  # さらに深く探索する
            return self.par[x]

    def unite(self, x, y):
        """x,yの属する集合のマージ"""
        x = self.find(x)  # xの根
        y = self.find(y)  # yの根
        if x == y:  # 同じ根を持つなら何もしない
            return
        if self.rank[x] < self.rank[y]:  # yの根のほうが深いとき
            self.par[x] = y
        else:
            self.par[y] = x
            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)


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

parent = [-1] * N
unionfind = UnionFind(N)
for i in range(M):
    xi, yi, zi = map(int, input().split())
    xi -= 1
    yi -= 1
    unionfind.unite(xi, yi)
    parent[yi] = xi

# print(parent)
# print(unionfind.par)
ans = len(set(unionfind.par))

print(ans)

Submission status: Wrong Answer

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

parent = [-1]*N
for i in range(M):
    xi, yi, zi = map(int, input().split())
    parent[yi - 1] = xi-1

# print(parent)

count = 0
for i in parent:
    if i == -1:
        count = count + 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as ddydd
from collections import deque as q
N, M = map(int, input().split())
XYZ = ddydd(list)
index = []
visited = [0] * (N + 1)
for _ in range(M):
  x, y, z = map(int, input().split())
  XYZ[x].append(y)
  XYZ[y].append(x)
  if x in index: continue
  index.append(x)
index = index[: : -1]
res = N
#group = 0
while index:
  temp = index.pop()
  Q = q([])
  Q.append(temp)
  visited[temp] = 1
  #group += 1
  while Q:
    temp = Q.popleft()
    for y in XYZ[temp]:
      if visited[y] == 0:
        res -= 1
        visited[y] = 1
      if y in index:
        Q.append(y)
        index.remove(y)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as ddydd
from collections import deque as q
N, M = map(int, input().split())
XYZ = ddydd(list)
index = []
visited = [0] * (N + 1)
for _ in range(M):
  x, y, z = map(int, input().split())
  XYZ[x].append(y)
  XYZ[y].append(x)
  if x in index: continue
  index.append(x)
index = index[: : -1]
res = N
#group = 0
while index:
  temp = index.pop()
  Q = q([])
  Q.append(temp)
  #group += 1
  while Q:
    temp = Q.popleft()
    for y in XYZ[temp]:
      if visited[y] == 0:
        res -= 1
        visited[y] = 1
      if y in index:
        Q.append(y)
        index.remove(y)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as ddydd
from collections import deque as q
N, M = map(int, input().split())
XYZ = ddydd(list)
link = []
start = 0
for _ in range(M):
  x, y, z = map(int, input().split())
  if start == 0:
    start = x
  XYZ[x].append(y)
  XYZ[y].append(x)
  if not x in link: link.append(x)
  if not y in link: link.append(y)

def searchPreMin(n):
  temp = min(XYZ[n])
  if temp < n:
    return searchPreMin(temp)
  else:
    return n
def searchPreMax(n):
  temp = max(XYZ[n])
  if temp > n:
    return searchPreMax(temp)
  else:
    return n
def searchMax(n):
  n = searchPreMin(n)
  return searchPreMax(n)

forest = []
nodes = len(link)
while link:
  temp = link.pop()
  tree = searchMax(temp)
  if not tree in forest: forest.append(tree)
    
print(N - nodes + len(forest))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as ddydd
from collections import deque as q
N, M = map(int, input().split())
XYZ = ddydd(list)
index = []
visited = [0] * (N + 1)
for _ in range(M):
  x, y, z = map(int, input().split())
  XYZ[x].append(y)
  if x in index: continue
  index.append(x)
index = index[: : -1]
res = N
#group = 0
while index:
  temp = index.pop()
  Q = q([])
  Q.append(temp)
  #group += 1
  while Q:
    temp = Q.popleft()
    for y in XYZ[temp]:
      if visited[y] == 0:
        res -= 1
        visited[y] = 1
      if y in index:
        Q.append(y)
        index.remove(y)
print(res)

Submission status: Wrong Answer

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

def parent(x):
    if card_parent[x] == x:
        return x
    else:
        return parent(card_parent[x])


for i in card_list:
    p, q = i[0], i[1]
    card_parent[p] = parent(p)
    card_parent[q] = parent(q)
    if card_parent[p] != card_parent[q]:
        if p < q:
            card_parent[q] = card_parent[p]
        else:
            card_parent[p] = card_parent[q]




card_parent = [ parent(i) for i in range(n) ]

print(len(set(card_parent)))

Submission status: Wrong Answer

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

print(len(set(card_parent)))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
X, Y, Z = [], [], []
card = []
cnt = 0

for i in range(m):
    x, y, z = map(int, input().split())
    X.append(x)
    Y.append(y)
    Z.append(z)

for x, y in zip(X, Y):
    if (x not in card) and (y not in card):
        card.append(x)
        card.append(y)
        cnt += 1
    elif x not in card:
        card.append(x)
    elif y not in card:
        card.append(y)

print(cnt + n - len(card))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M 
for i in range(M):
  X[i], Y[i], Z[i] = map(int, input().split())

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

for i in range(M) :
    reach[Y[i]-1].append(X[i])
    reach[X[i]-1].append(Y[i])

approach = [False for _ in range(N)]

def change(reach, s):       
    approach[s-1] = True
    for i in reach[s-1]:
        if not approach[i-1] :
            change(reach, i)

ans = 0
for i in range(N) :
    if not approach[i]:
        change(reach, i+1)
        ans += 1

print(approach)
print(reach)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
X, Y, Z = [], [], []
card = [i for i in range(1, n+1)]
cnt = 0

for i in range(m):
    x, y, z = map(int, input().split())
    X.append(x)
    Y.append(y)
    Z.append(z)

for x, y in zip(X, Y):
    if (x in card) and (y in card):
        card.remove(x)
        card.remove(y)
        cnt += 1
    elif x in card:
        card.remove(x)
    elif y in card:
        card.remove(y)

print(cnt + len(card))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
X, Y, Z = [], [], []
XX, YY, ZZ = [], [], []
card = [i for i in range(1, n+1)]
cnt = 0

for i in range(m):
    x, y, z = map(int, input().split())
    X.append(x)
    Y.append(y)
    Z.append(z)

for x, y, z in zip(X, Y, Z):
    if x != z and y != z:
        XX.append(x)
        YY.append(y)
        ZZ.append(z)
    else:
        if (x in card) and (y in card):
            card.remove(x)
            card.remove(y)
            cnt += 1
        elif x in card:
            card.remove(x)
        elif y in card:
            card.remove(y)

for x, y, z in zip(XX, YY, ZZ):
    if (x in card) and (y in card) and (z in card):
        card.remove(x)
        card.remove(y)
        card.remove(z)
        cnt += 2
    elif (x in card) and (y in card):
        card.remove(x)
        card.remove(y)
        cnt += 1
    elif (y in card) and (z in card):
        card.remove(y)
        card.remove(z)
        cnt += 1
    elif (z in card) and (x in card):
        card.remove(z)
        card.remove(x)
        cnt += 1
    elif x in card:
        card.remove(x)
    elif y in card:
        card.remove(y)
    elif z in card:
        card.remove(z)

print(cnt + len(card))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ans=[None]*n
p=0
a,b,c = map(int,input().split())
if c%2==0:
    ans[a-1]=ans[b-1]=1
else:
    ans[a-1]=1
    ans[b-1]=2
for i in range(m-1):
    a,b,c = map(int,input().split())
    if c%2==0:
        if ans[a-1]!=None and ans[b-1]!=None:
            p+=1
        elif ans[a-1]!=None and ans[b-1]==None:
            ans[b-1]=3-ans[a-1]
        elif ans[b-1]!=None and ans[a-1]==None:
            ans[a-1]=3-ans[b-1]
        else:
            ans[b-1]=ans[a-1]=1
    else:
        if ans[a-1]!=None and ans[b-1]!=None:
            p+=1
        elif ans[a-1]!=None and ans[b-1]==None:
            ans[b-1]=ans[a-1]
        elif ans[b-1]!=None and ans[a-1]==None:
            ans[a-1]=ans[b-1]
        else:
            ans[a-1]=1
            ans[b-1]=0
print(n-m+p)

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        elif self.rank[x] < self.rank[y]:
            x, y = y, x
            
        self.par[y] = x
    
    def get_par(self):
        return self.par

t = UnionFind(N)
for u, v, _ in edges:
    t.unite(u - 1, v - 1)

print(len(set(t.get_par())))

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x, y):
        if x > y:
            x, y = y, x
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
            
        self.par[y] = x
    
    def get_par(self):
        return self.par

t = UnionFind(N)
for u, v, _ in edges:
    t.unite(u - 1, v - 1)

print(len(set(t.get_par())))

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
            
        self.par[y] = x
    
    def get_par(self):
        return self.par

t = UnionFind(N)
for u, v, _ in edges:
    t.unite(u - 1, v - 1)
        
print(len(set(t.get_par())))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M 
unique = []
count = 0
for i in range(M):
  X[i], Y[i], Z[i] = map(int, input().split())
  if i == 0 :
    unique.append(X[i])
    unique.append(Y[i])
    count += 1
  else :
    if X[i] not in unique and Y[i] not in unique:
      unique.append(X[i])
      unique.append(Y[i])
      count += 1
    elif X[i] not in unique and Y[i] in unique:
      unique.append(X[i])
      count += 1
    elif X[i] in unique and Y[i] not in unique:
      unique.append(Y[i])
      count += 1    
    else:
      pass  

print(N-count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M 
unique = []
count = 0
for i in range(M):
  X[i], Y[i], Z[i] = map(int, input().split())

for i in range(M):
  if i == 0 :
    unique.append(X[i])
    unique.append(Y[i])
    count += 1
  else :
    if X[i] not in unique and Y[i] not in unique:
      unique.append(X[i])
      unique.append(Y[i])
      count += 1
    elif X[i] not in unique and Y[i] in unique:
      unique.append(X[i])
      count += 1
    elif X[i] in unique and Y[i] not in unique:
      unique.append(Y[i])
      count += 1    
    else:
      pass  

print(N-count)

Submission status: Wrong Answer

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

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

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

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

par = [0 for i in range(N)]
rnk = [0 for i in range(N)]

def init(n):
    for i in range(N):
        par[i] = i
        rnk[i] = 0

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if (rnk[x] < rnk[y]):
        par[x] = y
    else:
        par[y] = x
        if(rnk[x] == rnk[y]):
            rnk[x] += 1

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

for i in range(M):
    unite(X[i], Y[i])
print(len(set(par)))

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
	N, M = map(int, input().split())
	par = [ -1 for i in range(N)]

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

print(par.count(-1))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
x = [0 for i in range(n)]
y = [0 for i in range(n)]
for i in range(m):
    xi, yi, zi = map(int, input().split())
    if x[xi-1]==0 or y[yi-1]==0:
        x[xi-1]=x[xi-1]+1
        y[yi-1]=y[yi-1]+1

print(n-sum(x))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
x = []
y = []
for i in range(m):
    xi, yi, zi = map(int, input().split())
    if x.count(xi)==0 or y.count(yi)==0:
        x.append(xi)
        y.append(yi)

print(n-len(x))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
x = []
y = []
for i in range(m):
    xi, yi, zi = map(int, input().split())
    x.append(xi)
    y.append(yi)
    
x = set(x)
y = set(y)

print(max(n-m, n-len(x), n - len(y)))

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    E = []
    for _ in range(M):
        x, y, _ = map(int, input().split())
        E.append([x-1, y-1])
    
    # groups, num of groups
    ng = N
    g = [-1 for _ in range(N)]
    for e in E:
        x = e[0]
        y = e[1]
        if g[x] == -1 and g[y] == -1:
            ng -= 1
            g[x] = ng
            g[y] = ng
        elif g[x] == -1:
            g[x] = g[y]
            ng -= 1
        elif g[y] == -1:
            g[y] = g[x]
            ng -= 1
    print(ng)


main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**20
c=[[] for i in range(N)]
for i,j,w in edge:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
L=sorted([(len(c[i]),i) for i in range(N)],key=lambda x:x[0],reverse=True)
a=0
for l in L:
    if c[l[1]]==0:
        continue
    for n in c[l[1]]:
        c[n]=0
    c[l[1]]=0
    a+=1
print(a)

Submission status: Wrong Answer

Solution code:
class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(self.par[child]) == self.root(self.par[mas]):
            return
        else:
            self.par[child] = self.par[mas]

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False



n,m = map(int,input().split())
uf = uf_tree(n+1)
for i in range(m):
    x,y,z = map(int,input().split())
    uf.unite(x,y)

print(uf.indep()-1)

Submission status: Wrong Answer

Solution code:
class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.par[child] == self.par[mas]:
            return
        else:
            self.par[child] = self.par[mas]

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False



n,m = map(int,input().split())
uf = uf_tree(n+1)
for i in range(m):
    x,y,z = map(int,input().split())
    uf.unite(x,y)

print(uf.indep()-1)

Submission status: Wrong Answer

Solution code:
class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def coonect(self,child,mas):
        self.par[child] = self.par[mas]

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]
    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False


n,m = map(int,input().split())
uf = uf_tree(n+1)
for i in range(m):
    x,y,z = map(int,input().split())
    uf.coonect(x,y)

print(uf.indep()-1)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,size):
        self.par = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        
    def find(self,x):
        if self.par[x]==x:
            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 self.rank[x]>self.rank[y]:
            self.par[y]=x
        else:
            self.par[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1
    
    def same(self,x,y):
        x = self.find(x)
        y = self.find(y)
        return x==y
    
n,m = map(int,input().split())
tree = UnionFind(n)
for i in range(m):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    tree.union(x,y)
print(len(set(tree.par)))

Submission status: Wrong Answer

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
c = 0
group = set()
for n in range(1,N+1):
	if U[n] == 0:
		ans += 1
		continue
	elif n == U[n]:
		ans += 1
		group.add(U[n])
	elif U[n] in group:
		continue
	else:
		while(n != U[n] and U[n] not in group):
			group.add(U[n])
			n = U[n]
		group.add(U[n])
print(ans)

Submission status: Wrong Answer

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
c = 0
group = set()
for n in range(1,N+1):
	print(n,U[n])
	if U[n] == 0:
		ans += 1
		continue
	elif n == U[n]:
		ans += 1
		group.add(U[n])
	elif U[n] in group:
		continue
	else:
		while(n != U[n] and U[n] not in group):
			group.add(U[n])
			n = U[n]
		group.add(U[n])
print(ans)

Submission status: Wrong Answer

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 == U[u]:
		ans += 1
		group.add(u)
	elif u in group:
		group.add(u)
		continue
	else:
		while(u != U[u] and u not in group):
			group.add(u)
		group.add(u)
print(ans)

Submission status: Wrong Answer

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:
		group.add(u)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
lst = [i for i in range(N)]

def root(n):
    if n == lst[n]:
        return n
    lst[n] = root(lst[n])
    return lst[n]

def union(x,y):
    rootX, rootY = root(x), root(y)
    if rootX != rootY:
        if x > rootY:
            lst[x] = rootY
        if y > rootX:
            lst[y] = rootX

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

ans = len([i for i in range(N) if root(i) == i])
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
lst = [i for i in range(N)]

def root(n):
    if n == lst[n]:
        return n
    lst[n] = root(lst[n])
    return lst[n]

def union(x,y):
    rootX, rootY = root(x), root(y)
    if rootX != rootY:
        if x > y:
            lst[x] = rootY
        if y > x:
            lst[y] = rootX

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

ans = len([i for i in range(N) if root(i) == i])
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
lst = [i for i in range(N)]

def root(n):
    if n == lst[n]:
        return n
    lst[n] = root(lst[n])
    return lst[n]

def union(x,y):
    rootX, rootY = root(x), root(y)
    if rootX != rootY:
        lst[max(x,y)] = min(x,y)

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

ans = len([i for i in range(N) if root(i) == i])
print(ans)

Submission status: Wrong Answer

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

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

def func(n):
    if n == lst[n]:
        return n
    lst[n] = func(lst[n])
    return lst[n]
for i in range(N):
    func(i)

ans = len([i for i in range(N) if lst[i] == i])
print(ans)

Submission status: Wrong Answer

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

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

def func(n):
    if n == lst[n]:
        return n
    lst[n] = func(lst[n])
    return lst[n]

ans = len(set([func(i) for i in range(N)]))
print(ans)

Submission status: Wrong Answer

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

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

def func(n):
    if n == lst[n]:
        return n
    lst[n] = func(lst[n])
    return lst[n]

ans = len([i for i in range(N) if func(i) == i])
print(ans)

Submission status: Wrong Answer

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

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

def func(n):
    if n == lst[n]:
        return n
    lst[n] = func(lst[n])
    return lst[n]
for i in range(N):
    func(N-1-i)

ans = len([i for i in range(N) if lst[i] == i])
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lst = [i for i in range(N)]
for i in range(M):
    X,Y,Z = map(int,input().split())
    X -= 1
    Y -= 1
    lst[Y] = min(lst[Y], X)

def func(n):
    if n == lst[n]:
        return n
    lst[n] = func(lst[n])
    return lst[n]
for i in range(N):
    func(N-1-i)

ans = len([i for i in range(N) if lst[i] == i])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
cards = []
for i in range(0, N):
	cards.append(True)
cnt = 0
for i in range(0, M):
	X, Y, Z = map(int, input().split())
	if cards[X-1] and cards[Y-1]:
		cnt += 1
	cards[X-1] = False
	cards[Y-1] = False
for i in range(0, N):
	if cards[i]: cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.p[self.p[x]]
        return self.root(self.p[x])
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx is ry:
            return
        self.p[x] = y

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

    for i in range(M):
        x,y,_ = map(int, input().split())
        u.unite(x-1, y-1)

    rlist = set([])
    for i in range(N):
        parent = u.root(i)
        rlist.add(parent)

    print(len(rlist))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def root(table, i):
    if table[i] == i:
        return i
    table[i] = root(table, table[i])
    return table[i]


def union(table, a, b):
    table[min(a, b)] = root(table, max(a, b))


table = {}
n, m = map(int, input().split())
for _ in range(m):
    x, y, z = map(int, input().split())
    if x not in table:
        table[x] = x
    if y not in table:
        table[y] = y
    union(table, x, y)

s = set()
for i in range(1, n + 1):
    if i in table:
        s.add(root(table, i))
    else:
        s.add(i)

print(len(s))

Submission status: Wrong Answer

Solution code:

def root(table, i):
    if table[i] == i:
        return i
    table[i] = root(table, table[i])
    return table[i]

table = {}
n, m = map(int, input().split())
for _ in range(m):
    x, y, z = map(int, input().split())
    if x not in table:
        table[x] = x
    if y not in table:
        table[y] = y
    table[min(x, y)] = table[max(x, y)]

s = set()
for i in range(1, n + 1):
    if i in table:
        s.add(root(table, i))
    else:
        s.add(i)

print(len(s))