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:
def main():
    N,M = map(int, input().split())
    L = [[] for _ in range(N)]
    L[0].append(0)

    for i in range(M):
        x,y,z = map(int, input().split())
        L_exist = [x for x in L if x]
        for j,k in enumerate(L_exist):
            if (x in k) and not(y in k):
                L[j].append(y)
                break
            elif (y in k) and not(x in k):
                L[j].append(x)
                break
            elif (x in k) and (y in k):
                break
        else:
            L[len(L_exist)].append(x)
            L[len(L_exist)].append(y)

    a = [x for x in L if x]
    
    n=0
    for i in a:
        n += len(i)

    print((N-n+1)+len(a)-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    uf.unite(x, y)

c = Counter(uf.p)
ans = len(c)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
def dfs(i,c):
    visited[i]=1
    col[i] = c
    for j in edge[i]:
        if not visited[j[0]]:
            if j[1]%2==0:
                dfs(j[0],c)
            else:
                dfs(j[0],-1*c)
class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0]*N
        self.count = 0
    def root(self, a):
        if self.parent[a]==a:
            return a
        else:
            self.parent[a]=self.root(self.parent[a])
            return self.parent[a]
    def size(x):
        return -par[root(x)]

    def is_same(self, a, b):
        return self.root(a)==self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return

        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

def main():
    dd = defaultdict(int)
    n,m=map(int, input().split())
    uf = UnionFind(n)

    for i in range(m):
        x,y,z=map(int, input().split())
        uf.unite(x-1,y-1)
    print(len(set(uf.parent)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
def dfs(i,c):
    visited[i]=1
    col[i] = c
    for j in edge[i]:
        if not visited[j[0]]:
            if j[1]%2==0:
                dfs(j[0],c)
            else:
                dfs(j[0],-1*c)
class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0]*N
        self.count = 0
    def root(self, a):
        if self.parent[a]==a:
            return a
        else:
            self.parent[a]=self.root(self.parent[a])
            return self.parent[a]
    def size(x):
        return -par[root(x)]

    def is_same(self, a, b):
        return self.root(a)==self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return

        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

def main():
    dd = defaultdict(int)
    n,m=map(int, input().split())
    uf = UnionFind(n)
    edge = [[] for _ in range(n)]
    guki = [0]*n

    for i in range(m):
        x,y,z=map(int, input().split())
        uf.unite(x-1,y-1)
        edge[x-1].append([y-1,z%2])
        edge[y-1].append([x-1,z%2])

    for i in range(n):
        dd[uf.parent[i]]+=1
    print(len(dd))










if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
p = []
q = [-1 for i in range(n)]
r = 0
for i in range(m):
    x,y,z = map(int,input().split())
    p.append([x-1,y-1])
for i in range(m):
    if q[p[i][0]] == 0 and q[p[i][1]] == 0:
        r += 1
    else:
        q[p[i][0]] = 0
        q[p[i][1]] = 0
print(n-m+r)

Submission status: Wrong Answer

Solution code:
from collections import Counter
class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def same(self, x, y):
        return self.findSet(x) == self.findSet(y)

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

N, M = map(int, input().split())
# A = [0 for i in range(N+1)]
ds = DisjointSet(N)
for i in range(M):
    X, Y, Z = map(int, input().split())
    ds.unite(X-1, Y-1)

print(len(Counter(ds.p)))

Submission status: Wrong Answer

Solution code:
from collections import Counter
class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def same(self, x, y):
        return self.findSet(x) == self.findSet(y)

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

N, M = map(int, input().split())
# A = [0 for i in range(N+1)]
ds = DisjointSet(N+1)
for i in range(M):
    X, Y, Z = map(int, input().split())
    ds.unite(X, Y)

print(len(Counter(ds.p))-1)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import itertools
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
#ソートする！
#n=read()
n,m=reads()
ls=[]
for i in range(m):
    x,y,z=reads()
    ls.append((x,y))
ls=sorted(ls)
#print(ls)
gr=[]
dic={}
for i in range(m):
        x=ls[i][0] 
        y=ls[i][1] 
        if  y in dic:
            gr[dic[y]].add(x)
            dic[x]=dic[y]
        elif x in dic:
            gr[dic[x]].add(y)
            dic[y]=dic[x]
        else:
            gr.append({x,y})
            dic[x]=dic[y]=len(gr)-1
res=n
#print(gr)
for i in gr:
    res-=len(i)-1
print("{}".format(res))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import itertools
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
#ソートする！
#n=read()
n,m=reads()
ls=[]
for i in range(m):
    x,y,z=reads()
    ls.append((x,y)if x<y else (y,x))
ls=sorted(ls)
#print(ls)
gr=[]
dic={}
for i in range(m):
        x=ls[i][0] 
        y=ls[i][1] 
        if  y in dic:
            gr[dic[y]].add(x)
            dic[x]=dic[y]
        elif x in dic:
            gr[dic[x]].add(y)
            dic[y]=dic[x]
        else:
            gr.append({x,y})
            dic[x]=dic[y]=len(gr)-1
res=n
#print(gr)
for i in gr:
    res-=len(i)-1
print("{}".format(res))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import itertools
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
#ソートする！
#n=read()
ls=[]
n,m=reads()
for i in range(m):
    x,y,z=reads()
    ls.append((x,y))
ls=sorted(ls)
gr=[]
for i in range(m):
    x=ls[i][0] 
    y=ls[i][1] 
    denial=False
    for j in range(len(gr)):
        if  y in gr[j]:
            gr[j].add(x)
            denial=True
            break
        elif x in gr[j]:
            gr[j].add(y)
            denial=True
            break
    if not denial:
        gr.append({x,y})
res=n
for i in gr:
    res-=len(i)-1
print("{}".format(res))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
class UnionFind:
    #ノード番号は0-indexである
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)] 

    #UnionFindを初期化する関数
    def makeSet(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)]

    #ノードxのrootを探して返す関数
    def findRoot(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.findRoot(self.parents[x])
            return self.parents[x]

    #ノードxとノードyを連結する関数
    def uniteNode(self, x, y):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
            self.length[y] += self.length[x]
        else:
            self.parents[y] = x
            self.length[x] += self.length[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    #ノードxが含まれるグループの要素数を返す関数
    def getLength(self, x):
        x = self.findRoot(x)
        return self.length[x]        

    #ノードxとノードyが同じグループであるかを返す関数
    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

    #グループの数を返す関数
    def getNumberOfGroup(self):
        s = set()
        for i in self.parents:
            s.add(i)
        return len(s) 

def main():
    n, m = map(int, readline().split())
    uf = UnionFind(n)
    for _ in range(m):
        x, y, z = map(int, readline().split())
        uf.uniteNode(x-1, y-1)
    print(uf.getNumberOfGroup())
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#Union-Find 各操作の償却実行時間はO(α(n))
class UnionFind:
    #ノード番号は0-indexである
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)] 

    #UnionFindを初期化する関数
    def makeSet(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)]

    #ノードxのrootを探して返す関数
    def findRoot(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.findRoot(self.parents[x])
            return self.parents[x]

    #ノードxとノードyを連結する関数
    def uniteNode(self, x, y):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
            self.length[y] += self.length[x]
        else:
            self.parents[y] = x
            self.length[x] += self.length[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    #ノードxが含まれるグループの要素数を返す関数
    def getLength(self, x):
        x = self.findRoot(x)
        return self.length[x]        

    #ノードxとノードyが同じグループであるかを返す関数
    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for _ in range(m):
        x, y, z = map(int, input().split())
        x-=1
        y-=1
        uf.uniteNode(x, y)
    print(len(set(uf.parents)))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)] 

    def makeSet(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)]

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[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.parents[x] = y
            self.length[y] += self.length[x]
        else:
            self.parents[y] = x
            self.length[x] += self.length[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getLength(self, x):
        x = self.find(x)
        return self.length[x]        

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


def main():
    n, m = map(int, readline().split())
    uf = UnionFind(n)
    for _ in range(m):
        x, y, z = map(int, readline().split())
        x-=1
        y-=1
        z-=1
        uf.unite(x, y)
    s = set(uf.parents)
    print(len(s))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def find_base_label(lookup_table, label):
    base_label = label
    while lookup_table[base_label] != base_label:
        base_label = lookup_table[base_label]
    return base_label


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

    lookup_table = list(range(n))
    for _ in range(m):
        x, y, z = map(int, input().split())

        base_label_1 = find_base_label(lookup_table, x - 1)
        base_label_2 = find_base_label(lookup_table, y - 1)

        if base_label_1 < base_label_2:
            lookup_table[base_label_2] = base_label_1
        elif base_label_2 < base_label_1:
            lookup_table[base_label_1] = base_label_2

    print(len(set(lookup_table)))


main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
nums = [0] + [-1] * n
cnt = n
for _ in range(m):
  x,y,z = map(int,input().split())
  # 必要な処理：
  # x,yが−１であるかどうか
  # 魔法を使わないで良い奴があれば、その個数をcntからひく
  # x,y全部が1なら、±0
  # x,yの内、一つが1なら自ずと分かる奴が１つあるので、魔法を使わなくて良いのでcnt-1
  # x,yの内、どっちもわからなくても、-1
  if nums[x]==1 and nums[y]==1:
    continue
  else:
    cnt -= 1
    nums[x] = 1
    nums[y] = 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
nums = [0] + [-1] * n
cnt = n
for _ in range(m):
  x,y,z = map(int,input().split())
  # 必要な処理：
  # x,y,zが−１であるかどうか
  # 魔法を使わないで良い奴があれば、その個数をcntからひく
  # x,y,z全部が1なら、±0
  # x,y,zの内、２つが1なら自ずと分かる奴が１つあるので、魔法を使わなくて良いのでcnt-1
  # x,y,zの内、１つが-1なら魔法を使う奴がこれも-1
  if nums[x]==1 and nums[y]==1 and nums[z]==1:
    continue
  else:
    cnt -= 1
    nums[x] = 1
    nums[y] = 1
    nums[z] = 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
  u,v,z=map(int, input().split())
  g[u-1].append((u-1, v-1, z))
  g[v-1].append((v-1,u-1,z))
count = 0
renketu_list = [-1]*n
stack = []
for i in range(n):
  if renketu_list[i] == -1:
    count += 1
    renketu_list[i] = count
    while len(g[i]) > 0:
      stack.append(g[i].pop())
    while len(stack) > 0:
      u,v,z=stack.pop()
      if renketu_list == -1:
        renketu_list[v] = count
        while len(g[v])>0:
          stack.append(g[v].pop())

print(count)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in 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 union(self, x, y):
        xx = self.find(x)
        yy = self.find(y)
        if self.rank[xx] < self.rank[yy]:
            self.par[xx] = yy
        else:
            self.par[yy] = xx
            if self.rank[xx] == self.rank[yy]:
                self.rank[xx] += 1
        self.par[x] = self.find(x)
        self.par[y] = self.find(y)
                
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
n, m = map(int, input().split())
union = UnionFind(n)

for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    union.union(a, b)

print(len(set(union.par)))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in 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 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
                
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
n, m = map(int, input().split())
union = UnionFind(n)

for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    union.union(a, b)

print(len(set(union.par)))

Submission status: Wrong Answer

Solution code:
# import itertools
# import pprint
# import copy
import collections
# from collections import deque
# from fractions import gcd # >=Python3.5 # lcm = (a*b)//gcd(a,b)
# from math import gcd # <Python3.5
# from math import sqrt

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.par[x]

    # 併合
    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

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

n,m = map(int,input().split())
uf = UnionFind(n)

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

cnt = collections.Counter(uf.par)

print(len(set(cnt))-1)

Submission status: Wrong Answer

Solution code:
import collections
# from collections import deque
# from fractions import gcd # >=Python3.5 # lcm = (a*b)//gcd(a,b)
# from math import gcd # <Python3.5
# from math import sqrt

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.par[x]

    # 併合
    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

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

n,m = map(int,input().split())
uf = UnionFind(n)

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

# cnt = collections.Counter(uf.par)

# print(cnt)

# print(len(set(cnt))-1)

tank = set([])
for i in range(1,n):
    tank.add(uf.find(i))
print(len(tank))

Submission status: Wrong Answer

Solution code:
import collections
# from collections import deque
# from fractions import gcd # >=Python3.5 # lcm = (a*b)//gcd(a,b)
# from math import gcd # <Python3.5
# from math import sqrt

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.par[x]

    # 併合
    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

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

n,m = map(int,input().split())
uf = UnionFind(n)

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

cnt = collections.Counter(uf.par)

print(len(set(cnt))-1)

Submission status: Wrong Answer

Solution code:
import collections

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.par[x]

    # 併合
    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

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

n,m = map(int,input().split())
uf = UnionFind(n)

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

cnt = collections.Counter(uf.par)

print(cnt[0]-1 + len(set(cnt))-1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
seen=[0]*N
con=[[] for i in range(N)]
cnt=[[i,0] for i in range(N)]
for i in range(M):
    X,Y,Z=map(int,input().split())
    X,Y=X-1,Y-1
    con[X].append(Y)
    con[Y].append(X)
    cnt[X][1]+=1
    cnt[Y][1]+=1
cnt.sort(key=lambda x:x[1],reverse=True)
ans=0
for i,a in cnt:
    if(seen[i]):
        continue
    ans+=1
    seen[i]=1
    for v in con[i]:
        seen[v]=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(m)]
ans=[1]*n
a=list(range(n))
def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]
 
 
def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]
 
for i,j ,k in xy:
    unite(a,i-1,j-1)

print(len(list(set(a))))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(m)]
ans=[1]*n
a=list(range(n+1))
def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]
 
 
def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]
 
for i,j ,k in xy:
    ans[i-1]=0
    ans[j-1]=0
    unite(a,i,j)

print(len(list(set(a)))-1)

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split(' '))
    
    nums = list(range(N))
    dic = {n: n for n in nums}
    for _ in range(M):
        x, y, _ = map(int, input().split(' '))
        x, y = x - 1, y - 1

        result = min(nums[x], nums[y])
        dic[nums[x]] = result
        dic[nums[y]] = result
        nums[x] = result
        nums[y] = result
    
    for k, v in dic.items():
        k2, v2 = k, v
        while k2 != v2:
            k2 = v2
            v2 = dic[k2]
        dic[k] = v2
    nums = [dic[n] for n in nums]

    print(len(set(nums)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split(' '))
    
    nums = list(range(N))
    for _ in range(M):
        x, y, _ = map(int, input().split(' '))
        x, y = x - 1, y - 1

        result = min(nums[x], nums[y])
        nums[x] = result
        nums[y] = result

    print(len(set(nums)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l = [0] * N
num_list = [list(map(int, input().split())) for _ in range(M)]
num_list.sort()
ans = 0

for i in range(M):
  x, y, z = num_list[i][0], num_list[i][1], num_list[i][2]
  if (l[x-1] == 0) and (l[y-1] == 0):
    ans += 1
  l[x-1] = 1
  l[y-1] = 1
  
ans += N - sum(l)  
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l = [0] * N
num_list = [list(map(int, input().split())) for _ in range(M)]
num_list.sort()
ans = 0

for i in range(M):
  x, y, z = num_list[i][0], num_list[i][1], num_list[i][2]
  if (l[x-1] == 0) and (l[y-1] == 0):
    ans += 1
  l[x-1] = 1
  l[y-1] = 1
  
ans = ans + len(l) - sum(l)  
print(ans)

Submission status: Wrong Answer

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

for i in range(M):
  x, y, z = map(int, input().split())
  if (l[x-1] == 0) and (l[y-1] == 0):
    ans += 1
  l[x-1] = 1
  l[y-1] = 1
  
ans += N - sum(l)  
print(ans)

Submission status: Wrong Answer

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

for i in range(M):
  x, y, z = map(int, input().split())
  if (l[x-1] == 0) and (l[y-1] == 0):
    ans += 1
  l[x-1] = 1
  l[y-1] = 1
  
ans = ans + len(l) - sum(l)  
print(ans)

Submission status: Wrong Answer

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

for i in range(M):
  x, y, z = map(int, input().split())
  if (x not in l) and (y not in l):
    ans += 1
  l.append(x)
  l.append(y)
    
for i in range(1, N+1):
  if i not in l:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

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

for i in range(M):
  x, y, z = map(int, input().split())
  if (x in l) and (y not in l):
    l.append(y)
  elif (x not in l) and (y in l):
    l.append(x)
  elif (x not in l) and (y not in l):
    l.append(x)
    l.append(y)
    ans += 1
    
for i in range(1, N+1):
  if i not in l:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

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

for _ in range(M-1):
    X,Y,_ = map(int, input().split())
    s = 0
    for sub in l:
        if X in sub and Y not in sub:
            sub.append(Y)
            break

        elif X not in sub and Y in sub:
            sub.append(X)
            break

        elif X in sub and Y in sub:
            break

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

c = 0
for i in l:
    c += len(i)

print(len(l) + N - c)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
l = []
for i in range(M):
    X,Y,_ = map(int, input().split())
    check = False
    if i == 0:
        l.append([X,Y])
    else:
        for j in l:
            if X not in j and Y in j:
                j.append(X)
                check = True
                break

            elif Y not in j and X in j:
                j.append(Y)
                check = True
                break

            elif X in j and Y in j:
                check = True
                break

        if not check:
            l.append([X,Y])

c = 0       
for k in l:
    c += len(k)

print(len(l) + N - c)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]

    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 y < z:
            self.par[x] = y
        else:
            self.par[y] = x

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


n, m = map(int, input().split())

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

key = set()

for i in range(1, n+1):
  key.add(union.par[i])


print(len(key))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]

    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 y < z:
            self.par[x] = y
        else:
            self.par[y] = x

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


n, m = map(int, input().split())

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



key = union.par
for i in range(1, n+1):
  if key[key[i]] == key[i]:
    continue
  key[i] = key[key[i]]


print(len(set(key))-1)