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:
import heapq

N, M = map(int, input().split())
known = [0] * N
relation = [[] for _ in range(N)]
cost = 0
for _ in range(M):
  X, Y, Z = map(int, input().split())
  relation[X-1].append(Y-1)
  relation[Y-1].append(X-1)

pq = [(-len(relation[n]), n) for n in range(N)]
heapq.heapify(pq)

while len(pq) != 0:
  _, target = heapq.heappop(pq)
  if known[target] == 0:
    cost += 1
  known[target] = 1
  for card in relation[target]:
    known[card] = 1
print(cost)

Submission status: Wrong Answer

Solution code:
import heapq

N, M = map(int, input().split())
known = [0] * N
relation = [[] for _ in range(N)]
cost = 0
for _ in range(M):
  X, Y, Z = map(int, input().split())
  relation[X-1].append(Y-1)
  relation[Y-1].append(X-1)

pq = [(-len(relation[n]), n) for n in range(N)]
heapq.heapify(pq)

while len(pq) != 0:
  _, target = heapq.heappop(pq)
  if known[target] == 1:
    continue
  cost += 1
  known[target] = 1
  for card in relation[target]:
    known[card] = 1
print(cost)

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
root=[i for i in range(N)]
height=[0]*N
def find(a):
   f=a
   if a==root[a]:
      return a
   while a!=root[a]:
      a=root[a]
   root[f]=a
   return a
def union(a,b):
   A=find(a)
   B=find(b)
   if height[A]>height[B]:
      root[B]=root[A]
   else:
      root[A]=root[B]
      if height[A]==height[B]:
         height[B]+=1

for i in range(M):
   a,b,c=map(int,input().split())
   a-=1;b-=1
   union(a,b)
print(len(set(root)))

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size    
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
N,M = map(int,input().split())
uf = UnionFind(N)
for _ in range(M):
    x,y,z = map(int,input().split())
    uf.unite(x-1,y-1)
s = set(uf.parent)
print(len(s))

Submission status: Wrong Answer

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

count = 0
for i in range(M):
  x, y, z = map(int, input().split())
  if A[x-1] == -1 and A[y-1] == -1:
    count += 1
    A[x-1] = count
    A[y-1] = count
  elif A[x-1] == -1:
    A[x-1] = A[y-1]
  else:
    A[y-1] = A[x-1]
    
ans = count
for a in A:
  if a == -1:
    count += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]

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:
        pass
    par[x] = y
    size[y] += size[x]
    size[x] = 0

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

Ans =0
for j in size[1:]:
    if j != 0:
        Ans +=1
print(Ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]

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:
        pass
    par[x] = y
    size[y] += size[x]
    size[x] = 0

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

print(len(set(size[1:])))

Submission status: Wrong Answer

Solution code:


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in 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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
n,m=map(int,input().split())
uf1=UnionFind(n)

for i in range(m):
    x,y,x=map(int,input().split())
    x,y=x-1,y-1
    uf1.union(x,y)

for i in range(n):uf1.find(i)  
ans=set()
for i in uf1.par:
     ans.add(i)
print(len(ans))

Submission status: Wrong Answer

Solution code:
from collections import *
n,m=map(int,input().split())
v=[False for i in range(n)]
t=[[]for i in range(n)]
for i in range(m):
    x,y,x=map(int,input().split())
    x,y=x-1,y-1
    t[x].append(y)
    t[y].append(x)
ans=0
for i in range(n):
    if v[i]:
        continue
    else:
        ans+=1
        q=deque()
        for j in t[i]:           
            if v[j]==False:
                q.append(j)
        while q:
            k=q.popleft()
            v[k]=True
            for l in t[k]:
                if v[l]==False:
                    q.append(l)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import *
n,m=map(int,input().split())
v=[False for i in range(n)]
t=[[]for i in range(n)]
for i in range(m):
    x,y,x=map(int,input().split())
    x,y=x-1,y-1
    t[x].append(y)
    t[y].append(x)
ans=0
for i in range(n):
    if v[i]:
        continue
    else:
        ans+=1
        for j in t[i]:
            q=deque()
            if v[j]==False:
                q.append(j)
                while q:
                    k=q.popleft()
                    v[k]=True
                    for l in t[k]:
                        if v[l]==False:
                            q.append(l)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, collections

stdin = sys.stdin
n, m = map(int, stdin.readline().split())

par = [i for i in range(n)]
size = [1] * n  # size of tree
rank = [1] * n  # distance from parent


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


def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


for _ in range(m):
    x, y, z = map(int, stdin.readline().split())
    unite(x - 1, y - 1)

print(len(collections.Counter(par)))

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n

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

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        s = set()
        for par in self.par:
            s.add(par)
        return s
n,m = ma()
uf = unionfind(n)
for i in range(m):
    x,y,z = ma()
    uf.unite(x-1,y-1)
ls = [0]*n
for par in uf.par:
    ls[par]=1
print(sum(ls))

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n

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

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        s = set()
        for par in self.par:
            s.add(par)
        return s
n,m = ma()
uf = unionfind(n)
for i in range(m):
    x,y,z = ma()
    uf.unite(x-1,y-1)
s = uf.parent_set()
print(len(s))

Submission status: Wrong Answer

Solution code:
def abc126_e():
    n, m = map(int, input().split())
    par = [x for x in range(n)]
    rank = [0]*n

    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 rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]: rank[x] += 1

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

    ans = len(set(par))
    print(ans)

if __name__ == '__main__':
    abc126_e()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
List = []
for i in range (M):
  List.append(list(map(int, input().split())))
List.sort()
res =0
resList = [0]*N
for i in range(M):
  if resList[List[i][0]-1] == 0 and resList[List[i][1]-1] == 0:
    res +=1
    resList[List[i][0]-1] = 1 
    resList[List[i][1]-1] = 1
  else:
    resList[List[i][0]-1] = 1 
    resList[List[i][1]-1] = 1   
res += resList.count(0)
print(res)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
List = []
for i in range (M):
  List.append(list(map(int, input().split())))
res =0
resList = [0]*N
for i in range(M):
  if resList[List[i][0]-1] == 0 and resList[List[i][1]-1] == 0:
    res +=1
    resList[List[i][0]-1] = 1 
    resList[List[i][1]-1] = 1
  else:
    resList[List[i][0]-1] = 1 
    resList[List[i][1]-1] = 1   
res += resList.count(0)
print(res)

Submission status: Wrong Answer

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

flag=list(range(N))
def takeflag(p):
    stock=[]
    while flag[flag[p]]!=flag[p]:
        stock.append(p)
        p=flag[p]
    p=flag[p]
    for i in stock:
        flag[i]=p
    return p

for i in range(M):
    x,y,z = map(int,input().split())
    x,y=x-1,y-1
    x,y = map(takeflag,(x,y))
    x,y = min(x,y),max(x,y)
    flag[x]=y

st=set()
for i in range(N):
    st.add(flag[i])

print(len(st))

Submission status: Wrong Answer

Solution code:

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

flag=list(range(N))
def takeflag(p):
    stock=[]
    while flag[flag[p]]!=flag[p]:
        stock.append(p)
        p=flag[p]
    p=flag[p]
    for i in stock:
        flag[i]=p
    return p

for x,y,z in XYZ:
    flag[x-1]=y-1

st=set()
for i in range(N):
    st.add(takeflag(i))

print(len(st))

Submission status: Wrong Answer

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

c = 0
determined = set()

for x, y, z in XYZ:
    if x not in determined and y not in determined:
        c += 1
    determined.add(x)
    determined.add(y)

c += N - len(determined)

print(c)

Submission status: Wrong Answer

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

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

class Union_Find:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for i in range(n)]
    
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
    
    def unite(self, x, y):
        if self.find(x) == self.find(y):
            return
        if self.rank[x] == self.rank[y]:
            self.parent[y] = x
            self.rank[x] += 1
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y

uftree = Union_Find(N+1)

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

result = 0
for i in range(1, N+1):
    if uftree.find(i) == i:
        result += 1

print(result)

Submission status: Wrong Answer

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

class Union_Find:
    def __init__(self,n):
        self.parent_l = [i for i in range(n)]
        self.rank_l = [1 for i in range(n)]
    
    def find(self,x):
        if self.parent_l[x] == x:
            return x
        else:
            par = self.find(self.parent_l[x])
            self.parent_l[x] = par
            return par
    
    def unite(self, x, y):
        if self.rank_l == self.rank_l:
            self.parent_l[y] = x
            self.rank_l[x] += 1
        elif self.rank_l > self.rank_l:
            self.parent_l[y] = x
        else:
            self.parent_l[x] = y

uftree = Union_Find(N+1)

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

result = 0
for i in range(1, N+1):
    if uftree.find(i) == i:
        result += 1

print(result)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x_memo = [0] * (n + 1)
y_memo = [0] * (n + 1)

ans = n
for i in range(m):
    x, y, _ = map(int, input().split())
    if x_memo[x] != 1 and y_memo[y] != 1:
        x_memo[x] = 1
        y_memo[y] = 1
        ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
XYZs = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

groups = [-1 for _ in range(N)]
connections = set()

now = 0
for XYZ in XYZs:
    if groups[XYZ[0]] == -1 and groups[XYZ[1]] == -1:
        now += 1
        groups[XYZ[0]] = now
        groups[XYZ[1]] = now
    elif groups[XYZ[0]] == -1:
        groups[XYZ[0]] = groups[XYZ[1]]
    elif groups[XYZ[1]] == -1:
        groups[XYZ[1]] = groups[XYZ[0]]
    elif groups[XYZ[0]] != groups[XYZ[1]]:
        if groups[XYZ[0]] > groups[XYZ[1]]:
            connections.add(str(groups[XYZ[1]])+"-"+str(groups[XYZ[0]]))
        else:
            connections.add(str(groups[XYZ[0]])+"-"+str(groups[XYZ[1]]))


answer = 0
for i in range(N):
    if groups[i] == -1:
        answer+=1
connections_list = []
for connection in connections:
    connections_list.append(list(map(int,connection.split("-"))))

connections_list = sorted(connections_list)
groups_set = set([i for i in range(now)])

for connection in connections_list:
    if connection[0] in groups_set:
        groups_set.remove(connection[0])

print(answer+len(groups_set))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
XYZs = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

groups = [-1 for _ in range(N)]
connections = set()

now = 0
for XYZ in XYZs:
    if groups[XYZ[0]] == -1 and groups[XYZ[1]] == -1:
        now += 1
        groups[XYZ[0]] = now
        groups[XYZ[1]] = now
    elif groups[XYZ[0]] == -1:
        groups[XYZ[0]] = groups[XYZ[1]]
    elif groups[XYZ[1]] == -1:
        groups[XYZ[1]] = groups[XYZ[0]]
    elif groups[XYZ[0]] != groups[XYZ[1]]:
        if groups[XYZ[0]] > groups[XYZ[1]]:
            connections.add(str(groups[XYZ[1]])+"-"+str(groups[XYZ[0]]))
        else:
            connections.add(str(groups[XYZ[0]])+"-"+str(groups[XYZ[1]]))

answer = 0
for i in range(N):
    if groups[i] == -1:
        answer+=1

print(answer+now-len(connections))

Submission status: Wrong Answer

Solution code:
from collections import deque

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1 for _ in range(n)]
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(x,y): return self.find(x)==self.find(y)
    def size(x): return -self.d[self.find(x)]

N,M=map(int,input().split())
uf = UnionFind(N+1)
G=[{} for _ in range(N+1)]
for i in range(M):
  x,y,z=map(int,input().split())
  uf.unite(x,y)
  G[x][y]=z
  G[y][x]=z
  
def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque([])
    now = s
    seen[now]=1
    todo.append(now)
    unique=False
    while not unique:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + G[a][b]
        else:
          if d[b] % 2 != (d[a] + G[a][b]) % 2:
            unique=True
            break
    return unique

d = uf.d
count=0
group=set()
for i in range(1,N+1):
  if d[i]==-1:
    count += 1
  if d[i]>0:
    group.add(d[i])

count2 = 0
for i in list(group):
  if not bfs(i):
    count2 += 1
    
print(count+count2)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n=0):
        self.d = [-1 for _ in range(n)]
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(x,y): return self.find(x)==self.find(y)
    def size(x): return -self.d[self.find(x)]

N,M=map(int,input().split())
uf = UnionFind(N+1)
for i in range(M):
  x,y,z=map(int,input().split())
  uf.unite(x,y)

d = uf.d
count=0
group=set()
for i in range(1,N+1):
  if d[i]==-1:
    count += 1
  if d[i]>0:
    group.add(d[i])

print(count+len(group))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * 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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.size[x] < self.size[y]:
                x,y = y,x
            self.parents[y] = x
            self.size[x] += self.size[y]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        X, Y, Z = map(lambda x: int(x)-1, input().split())
        uf.union(uf.find(X), uf.find(Y))
    print(len(set(uf.parents)))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
ans = [-1]*n
for i in range(m):
  x,y,z = map(int, input().split())
  ans[y-1] = x-1
cnt = 0
for i in ans:
  if i < 0:
    cnt += 1
  
print(cnt)

Submission status: Wrong Answer

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


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

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

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

Submission status: Wrong Answer

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


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

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

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

Submission status: Wrong Answer

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

class UnionFind():
    def __init__(self, n):
        self.li = list(range(n))
    def root(self, x):
        if self.li[x]==x:
            return x
        self.li[x] = self.root(self.li[x])
        return self.li[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx==ry:
            return
        self.li[ry] = rx
    def same(self, x, y):
        return self.root(x)==self.root(y)

uf = UnionFind(n)
for x, y in xy:
    uf.unite(x, y)
print(len(set(uf.li)))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ans=[i for i in range(N)]
for _ in range(M):
    X,Y,_=map(int,input().split())
    X,Y=X-1,Y-1
    if X>Y:
        X,Y=Y,X
    ans[Y]=ans[X]
tmp=0
for i in range(N):
    if i==ans[i]:
        tmp+=1
print(tmp)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    n,m=map(int,input().split())
    graph=[[] for _ in range(n+1)]
    for i in range(m):
        a,b,c=map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    stack=[]
    visited=[0 for _ in range(n+1)]

    zones=0
    count=0
    def DFS():
        c=1
        while True:
            if len(stack)==0:
                break
            s=stack.pop()
            if visited[s]==0:
                stack.append(s)

                visited[s]=1
                c+=1
            if len(stack)==0:
                break
        return c
    for i in range(1,n+1):
        if visited[i]==0:
            visited[i]=1
            for j in graph[i]:
                stack.append(j)
            count+=DFS()
        else:
            continue
        zones+=1
    print(n-count+zones)





if __name__ == "__main__":

    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
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())
a = [[i] for i in range(n)]
for i in range(m):
    a[x[i] - 1].append(y[i] - 1)
    a[y[i] - 1].append(x[i] - 1)
a.sort(reverse=True, key=lambda x:len(x))
# print("a =", a)
b = [0 for i in range(n)]
ans = 0
c = []
for i in range(n):
    index1 = bisect_left(c, a[i][0])
    if index1 == len(c) or c[index1] != a[i][0]:
        ans += 1
    c += a[i][1:]
    c.sort()
print(ans)