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:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(*args):
    print(*args,file=sys.stderr)

def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
     
#input
class UnionFindTree():
    def __init__(self,n):
        self.uft=[i for i in range(n+1)]#やっぱり0-indexedが一番だね
    def root (self,a):
        if self.uft[a]==a:
            return a
        else:
            az=self.root(self.uft[a])
            self.uft[a]=az
            return az
    def find(self,a,b):
        return self.root(a)==self.root(b)
    
    def union(self,a,b):
        if not self.find(a,b):
            s,t=min(a,b),max(a,b)
            self.uft[t]=s

class UftWRank(UnionFindTree):
    def __init__(self,n):
        super().__init__(n)
        self.rank=[0]*(n+1)
    def union(self,a,b):
        if not self.find(a,b):
            #rankの小さい方をでかい方のrootにつけるイメージ
            A,B=self.rank[a],self.rank[b]
            if A<B:
                self.uft[b]=a
            else:
                self.uft[a]=b
                if A==B:self.rank[a]+=1
                
def resolve():
    n,q=pin()
    tr=UnionFindTree(n)#1-indexed rootの場所が書かれてある
    for query in range(q):
        a,b,f=pin()
        tr.union(a,b)
        #printargs2err(tr.uft,tr.rank)
    for vert in range(n+1):
        tr.root(vert)
    debug(tr.uft)
    tr.uft.pop(0)
    from collections import Counter
    print(len(Counter(tr.uft)))#はい。0-indexedなので1を引きます。0番目の数は存在しないからです
    #print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
#if __name__=="__main__":resolve()

"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 1
1 2 1"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 5
4 5 4
1 3 3
1 2 1
2 3 2
5 6 5"""
        output = """2"""
        self.assertIO(input, output)
        
if __name__=="__main__":resolve()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(*args):
    print(*args,file=sys.stderr)

def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
     
#input
class UnionFindTree():
    def __init__(self,n):
        self.uft=[i for i in range(n+1)]#やっぱり0-indexedが一番だね
    def root (self,a):
        if self.uft[a]==a:
            return a
        else:
            az=self.root(self.uft[a])
            self.uft[a]=az
            return az
    def find(self,a,b):
        return self.root(a)==self.root(b)
    
    def union(self,a,b):
        if not self.find(a,b):
            s,t=min(a,b),max(a,b)
            self.uft[t]=s

class UftWRank(UnionFindTree):
    def __init__(self,n):
        super().__init__(n)
        self.rank=[0]*(n+1)
    def union(self,a,b):
        if not self.find(a,b):
            #rankの小さい方をでかい方のrootにつけるイメージ
            A,B=self.rank[a],self.rank[b]
            if A<B:
                self.uft[b]=a
            else:
                self.uft[a]=b
                if A==B:self.rank[a]+=1
                
def resolve():
    n,q=pin()
    tr=UnionFindTree(n)#1-indexed rootの場所が書かれてある
    for query in range(q):
        a,b,f=pin()
        tr.union(a,b)
        #printargs2err(tr.uft,tr.rank)
    for vert in range(n+1):
        tr.root(vert)
    from collections import Counter
    print(len(Counter(tr.uft))-1)
    #print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
#if __name__=="__main__":resolve()

"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 1
1 2 1"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """100000 1
1 100000 100"""
        output = """99999"""
        self.assertIO(input, output)

if __name__=="__main__":resolve()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(*args):
    print(*args,file=sys.stderr)

def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
     
#input
class UnionFindTree():
    def __init__(self,n):
        self.uft=[i for i in range(n+1)]#やっぱり0-indexedが一番だね
    def root (self,a):
        if self.uft[a]==a:
            return a
        else:
            az=self.root(self.uft[a])
            self.uft[a]=az
            return az
    def find(self,a,b):
        return self.root(a)==self.root(b)
    
    def union(self,a,b):
        if not self.find(a,b):
            s,t=min(a,b),max(a,b)
            self.uft[t]=s

class UftWRank(UnionFindTree):
    def __init__(self,n):
        super().__init__(n)
        self.rank=[0]*(n+1)
    def union(self,a,b):
        if not self.find(a,b):
            #rankの小さい方をでかい方のrootにつけるイメージ
            A,B=self.rank[a],self.rank[b]
            if A<B:
                self.uft[b]=a
            else:
                self.uft[a]=b
                if A==B:self.rank[a]+=1
                
def resolve():
    n,q=pin()
    tr=UftWRank(n)#1-indexed rootの場所が書かれてある
    for query in range(q):
        a,b,f=pin()
        tr.union(a,b)
        #printargs2err(tr.uft,tr.rank)
    for vert in range(n+1):
        tr.root(vert)
    from collections import Counter
    print(len(Counter(tr.uft))-1)
    #print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
#if __name__=="__main__":resolve()

"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 1
1 2 1"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """100000 1
1 100000 100"""
        output = """99999"""
        self.assertIO(input, output)

if __name__=="__main__":resolve()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(*args):
    print(*args,file=sys.stderr)

def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
     
#input
class UnionFindTree():
    def __init__(self,n):
        self.uft=[i for i in range(n+1)]#やっぱり0-indexedが一番だね
    def root (self,a):
        if self.uft[a]==a:
            return a
        else:
            az=self.root(self.uft[a])
            self.uft[a]=az
            return az
    def find(self,a,b):
        return self.root(a)==self.root(b)
    
    def union(self,a,b):
        if not self.find(a,b):
            s,t=min(a,b),max(a,b)
            self.uft[t]=s

class UftWRank(UnionFindTree):
    def __init__(self,n):
        super().__init__(n)
        self.rank=[0]*(n+1)
    def union(self,a,b):
        if not self.find(a,b):
            #rankの小さい方をでかい方のrootにつけるイメージ
            A,B=self.rank[a],self.rank[b]
            if A<B:
                self.uft[b]=a
            else:
                self.uft[a]=b
                if A==B:self.rank[a]+=1
                
def resolve():
    n,q=pin()
    tr=UftWRank(n)#1-indexed rootの場所が書かれてある
    for query in range(q):
        a,b,f=pin()
        tr.union(a,b)
        #printargs2err(tr.uft,tr.rank)
    for vert in range(n):
        tr.root(vert)
    from collections import Counter
    print(len(Counter(tr.uft))-1)
    #print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
#if __name__=="__main__":resolve()

"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 1
1 2 1"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """100000 1
1 100000 100"""
        output = """99999"""
        self.assertIO(input, output)

if __name__=="__main__":resolve()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
print(len(set(range(1, N + 1)) - {int(input().split()[1]) for _ in range(M)}))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**5)

def dfs(num,log):
    for item in way[num]:
        if root[item]==item:
            dfs(item,log)
    root[num]=min(log,root[num])
    return 

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

root=[i for i in range(N)]
way=[[] for i in range(N)]
order=[]

for _ in range(M):
    X,Y,Z=map(int,input().split())
    X,Y=min(X,Y),max(X,Y)
    order.append([X-1,Y-1,Z])

order.sort(key=lambda x:(x[0],x[1]))

for item in order:
    way[item[0]].append(item[1])

for i in range(N):
    if root[i]==i:
        dfs(i,i)
        
root=list(set(root))
print(len(root))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**5)

def dfs(num,log):
    for item in way[num]:
        if root[item]==-1:
            dfs(item,log)
    root[num]=log
    return 

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

root=[-1 for i in range(N)]
way=[[] for i in range(N)]
order=[]

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

order.sort(key=lambda x:(x[0],x[1]))

for item in order:
    way[item[0]].append(item[1])

for i in range(N):
    if root[i]==-1:
        dfs(i,i)
root=list(set(root))
print(len(root))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**5)

def dfs(num,log):
    for item in way[num]:
        if root[item]==item:
            dfs(item,log)
    root[num]=min(log,root[num])
    return 

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

root=[i for i in range(N)]
way=[[] for i in range(N)]
order=[]

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

order.sort(key=lambda x:(x[0],x[1]))

for item in order:
    way[item[0]].append(item[1])

for i in range(N):
    if root[i]==i:
        dfs(i,i)
root=list(set(root))
print(len(root))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**5)

def dfs(num,log):
    for item in way[num]:
        if root[item]==item:
            dfs(item,log)
    root[num]=log
    return 

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

root=[i for i in range(N)]
way=[[] for i in range(N)]
order=[]

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

order.sort(key=lambda x:(x[0],x[1]))

for item in order:
    way[item[0]].append(item[1])

for i in range(N):
    if root[i]==i:
        dfs(i,i)
root=list(set(root))
print(len(root))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
isknown = [False]*(N+1)
ans = 0

d = defaultdict(list)
for _ in range(M):
    x, y, z = map(int, input().split())
    d[x].append(y)
    d[y].append(x)

for i, j in sorted(d.items(),key=lambda x:-len(x[1])):
    if not isknown[i] and not any([isknown[i] for i in d[i]]):
        ans += 1

    isknown[i] = True
    for k in j:
        isknown[k] = True

ans += isknown[1:].count(False)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
isknown = [False]*(N+1)
ans = 0

d = defaultdict(list)
for _ in range(M):
    x, y, z = map(int, input().split())
    d[x].append(y)
    d[y].append(x)

for i, j in sorted(d.items(),key=lambda x:-len(x[1])):
    if not isknown[i]:
        ans += 1
    isknown[i] = True
    for k in j:
        isknown[k] = True

ans += isknown[1:].count(False)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
isknown = [False]*(N+1)
ans = 0

d = defaultdict(list)
for _ in range(M):
    x, y, z = map(int, input().split())
    d[x].append(y)
    d[y].append(x)

for i, j in sorted(d.items(),key=lambda x:-len(x[1])):
    if isknown[i]:continue
    ans += 1
    isknown[i] = True
    for k in j:
        isknown[k] = True

ans += isknown[1:].count(False)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
isknown = [False]*(N+1)
ans = 0

for _ in range(M):
    x, y, z = map(int, input().split())
    if isknown[x]:
        isknown[y] = True
        continue
    if isknown[y]:
        isknown[x] = True
        continue

    ans += 1
    isknown[y] = True
    isknown[x] = True

ans += isknown[1:].count(False)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().rstrip().split()]
x = c = 0
L = {}
disting = []
for m in range(M):
    X,Y,Z = [int(i) for i in input().rstrip().split()]
    if (X in L) ^ (Y in L):
        try:
            L[X] = L[Y]
        except:
            L[Y] = L[X]
    elif (X in L) and (Y in L):
        if L[X] != L[Y]:
            d = sorted([L[X],L[Y]])
            if not d in disting:
                c -= 1
                disting += [d]
    else:
        x += 1
        c += 1
        L[X] = L[Y] = x

    #print(L)
other = len([v for v in range(1,N+1) if not v in L])
print(c+other)

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().rstrip().split()]
x = c = 0
L = {}
for m in range(M):
    X,Y,Z = [int(i) for i in input().rstrip().split()]
    if (X in L) ^ (Y in L):
        try:
            L[X] = L[Y]
        except:
            L[Y] = L[X]
    elif (X in L) and (Y in L):
        if L[X] != L[Y]:
            c -= 1
    else:
        x += 1
        c += 1
        L[X] = L[Y] = x

    print(L)
other = len([v for v in range(1,N+1) if not v in L])
print(c+other)

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().rstrip().split()]
x = 0
L = {}
for m in range(M):
    X,Y,Z = [int(i) for i in input().rstrip().split()]
    if X in L or Y in L:
        try:
            L[X] = L[Y]
        except:
            L[Y] = L[X]
    else:
        x += 1
        L[X] = L[Y] = x

#print(L)
other = len([x for x in range(1,N+1) if not x in L])
print(x+other)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
  x, y, z = map(int, input().split())
  adj[x-1].append(y-1)
  adj[y-1].append(x-1)
opn = [True] * n
count = 0
for i in range(n):
  if opn:
    count += 1
    opn[i] = False
    stack = [i]
    while stack:
      u = stack.pop()
      for v in adj[u]:
        if opn[v]:
          stack.append(v)
          opn[v] = False
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 for _ in range(N)]
        self.size = [1 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]:
                self.rank[x] += 1
            elif self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

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

print(len(set(uf.par)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    use = [False for _ in range(N)]
    formula = 0
    for i in range(M):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        if (use[x] == True and use[y] == True):
            continue
        else:
            use[x],use[y] = True,True
            formula += 1
            
    print(N-formula)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
xyz = sorted([list(map(int, input().split())) for _ in range(m)])
d = {i: i for i in range(1, n+1)}
for x, y, z in xyz :
  a, b = sorted([x, y])
  g = min(d[a], d[b])
  d[b] = d[a] = g

print(len(set(d.values())))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
xyz = sorted([list(map(int, input().split())) for _ in range(m)])
d = {i: i for i in range(1, n+1)}
for x, y, z in xyz :
  a, b = sorted([x, y])
  d[b] = d[a]

print(len(set(d.values())))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
xyz = sorted([list(map(int, input().split())) for _ in range(m)])
s = set(i+1 for i in range(n))
for x, y, z in xyz :
  removal = min(x, y)
  if removal in s:
    s.remove(removal)

print(len(s))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = set(i+1 for i in range(n))
for _ in range(m):
  x, y, z = map(int, input().split())
  removal = max(x, y)
  if removal in s:
    s.remove(removal)

print(len(s))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
xy = [[] for i in range(N)]
alr = [1 for i in range(N)]
for i in range(M):
    x,y,z = map(int,input().split())
    xy[x-1].append(y-1)
    alr[x-1] = 0
    alr[y-1] = 0
count = sum(alr)
stack = []
for i in range(N):
    if not alr[i]:
        stack.append(xy[i])
        alr[i] = 1
        if xy[i]:
            count += 1
        while stack:
            now = stack.pop()
            for j in now:
                if not alr[j]:
                    alr[j] = 1
                    stack.append(xy[j])
print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
xy = [[] for i in range(N)]
alr = [1 for i in range(N)]
for i in range(M):
    x,y,z = map(int,input().split())
    xy[x-1].append(y-1)
    alr[x-1] = 0
    alr[y-1] = 0
count = sum(alr)
stack = []
for i in range(N):
    if not alr[i]:
        stack.append(xy[i])
        alr[i] = 1
        count += 1
        while stack:
            now = stack.pop()
            for j in now:
                if not alr[j]:
                    alr[j] = 1
                    stack.append(xy[j])
print(count)

Submission status: Wrong Answer

Solution code:
nm=list(map(int,input().split()))
a=[0]*(nm[0]+1)
bond=[]
for i in range(nm[1]):
    xyz=list(map(int,input().split()))
    if xyz[1]==xyz[2]:
        a[xyz[0]]=2
    elif xyz[0]==xyz[2]:
        a[xyz[1]]=2
    else:
        if a[xyz[2]]==2:
            if a[xyz[0]]==2:
                a[xyz[1]]=2
            elif a[xyz[0]]==1:
                a[xyz[1]]=1
            elif a[xyz[1]]==2:
                a[xyz[0]]=2
            elif a[xyz[1]]==1:
                a[xyz[0]]=1
            else:
                bond.append([min(xyz[0],xyz[1]),max(xyz[0],xyz[1]),0])
        elif a[xyz[2]]==1:
            if a[xyz[0]]==2:
                a[xyz[1]]=1
            elif a[xyz[0]]==1:
                a[xyz[1]]=2
            elif a[xyz[1]]==2:
                a[xyz[0]]=1
            elif a[xyz[1]]==1:
                a[xyz[0]]=2
            else:
                bond.append([min(xyz[0],xyz[1]),max(xyz[0],xyz[1]),1])
        else:
            if a[xyz[0]]==2:
                bond.append([min(xyz[1],xyz[2]),max(xyz[1],xyz[2]),0])
            elif a[xyz[0]]==1:
                bond.append([min(xyz[1],xyz[2]),max(xyz[1],xyz[2]),1])
            elif a[xyz[1]]==2:
                bond.append([min(xyz[0],xyz[2]),max(xyz[0],xyz[2]),0])
            elif a[xyz[1]]==1:
                bond.append([min(xyz[0],xyz[2]),max(xyz[0],xyz[2]),1])
bond.sort()
tbond=bond
flag=0
while flag<2:
    bond=tbond
    tbond=[]
    through=0
    for i in range(len(bond)):
        if a[bond[i][0]]!=0:
            if bond[i][2]==0:
                a[bond[i][1]]=a[bond[i][0]]
                tbond.append(bond[i])
                continue
            else:
                a[bond[i][1]]=2//a[bond[i][0]]
                tbond.append(bond[i])
                continue
        elif a[bond[i][1]]!=0:
            if bond[i][2]==0:
                a[bond[i][0]]=a[bond[i][1]]
                tbond.append(bond[i])
                continue
            else:
                a[bond[i][0]]=2//a[bond[i][1]]
                tbond.append(bond[i])
                continue
        else:
            through+=1
    if through==len(bond):
        flag+=1
ans=0
for i in range(nm[0]):
    if a[i]==0:
        ans+=1
if ans==nm[0]:
    ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def visit_tree(now, num):
    visited[now] = num
    for i in range(len(tree[now])):
        if not visited[now]:
            visit_tree(tree[now][i], num)

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

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)

Submission status: Wrong Answer

Solution code:
def visit_tree(now, num):
    if not visited[now]:
        visited[now] = num
        # for i in range(len(tree[now])):
        #     visit_tree(tree[now][i], num)

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

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)

Submission status: Wrong Answer

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

XYZ.sort(key=lambda x:x[0]) #Xでソート(YはXより大きいことが保証されている)

#情報のつながりがあるカードでグルーピングする
#グループIDのリスト(0は未割り当て)
G=[0]*(N+1)

ans=0
for x,y,z in XYZ:
    if G[y]: G[x]=G[y] #yがグルーピング済みならxも同じグループへ
    elif G[x]: G[y]=G[x] #yがグルーピング済みでなくxがグルーピング済みなら同じグループへ
    else:
        ans+=1
        G[x]=G[y]=ans #新規グループへ

#グルーピングされてないカードを1枚だけのグループに割り当て
for i in range(1,N+1):
    if G[i]==0: ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import os, sys, re, math, queue

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

set_ary = []
used = set()

def add_element(x):
	for s in set_ary:
		if x in s:
			s.add(x)

for _ in range(M):
	x,y,z = list(map(int,input().split(' ')))
	if z % 2 == 0:
		if x in used or y in used:
			for s in set_ary:
				if x in s or y in s:
					s.add(x)
					s.add(y)
		else:
			set_ary.append(set([x,y]))
	else:
		if x in used:
			add_element(x)
		else:
			set_ary.append(set([x]))
		if y in used:
			add_element(y)
		else:
			set_ary.append(set([y]))
	used.add(x)
	used.add(y)
			
ret = math.ceil(len(set_ary) / 2)
ret += N - len(used)
print(ret)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, id):
        if id != self.parent[id]:
            self.parent[id] = self.find(self.parent[id])
        return self.parent[id]

    def union(self, id1, id2):
        par1, par2 = self.find(id1), self.find(id2)
        if par1 == par2:
            return 0
        if self.rank[par1] > self.rank[par2]:
            self.parent[par2] = par1
        else:
            self.parent[par1] = par2
            if self.rank[par1] == self.rank[par2]:
                self.rank[par2] += 1

nVertices, nEdges = map(int, input().split())
unionFind = UnionFind(nVertices)
for _ in range(nEdges):
    u, v, _ = map(lambda x: int(x) - 1, input().split())
    unionFind.union(u, v)
print(len(set(unionFind.parent)))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, id):
        if id != self.parent[id]:
            self.parent[id] = self.find(self.parent[id])
        return self.parent[id]

    def union(self, id1, id2):
        par1, par2 = self.find(id1), self.find(id2)
        if par1 == par2:
            return 0
        if self.rank[par1] > self.rank[par2]:
            self.parent[par2] = par1
        else:
            self.parent[par1] = par2
            if self.rank[par1] == self.rank[par2]:
                self.rank[par2] += 1

nVertices, nEdges = map(int, input().split())
unionFind = UnionFind(nVertices)
for _ in range(nEdges):
    u, v, _ = map(lambda x: int(x) - 1, input().split())
    unionFind.union(u, v)
print(len(set(unionFind.parent)))

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split(' ')))

shozoku = {}
pt = 0
ans = 0
for i in range(k):
    a, b, z = list(map(int, input().split(' ')))
    if a not in shozoku and b not in shozoku:
        shozoku[a] = pt
        shozoku[b] = pt
        pt += 1
        ans += 1
    elif a in shozoku and b in shozoku:
        if shozoku[a] != shozoku[b]:
            ans -= 1
#            
#            for k, v in shozoku.items():
#                if v == shozoku[b]:
#                    shozoku[k] = shozoku[a]
    elif a in shozoku:
        shozoku[b] = shozoku[a]
    elif b in shozoku:
        shozoku[a] = shozoku[b]

used = {}
for i in range(1, n+1):
    if i not in shozoku:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split(' ')))

shozoku = {}
pt = 0
ans = 0
for i in range(k):
    a, b, z = list(map(int, input().split(' ')))
    if a not in shozoku and b not in shozoku:
        shozoku[a] = pt
        shozoku[b] = pt
        pt += 1
        ans += 1
    elif a in shozoku and b in shozoku:
        if shozoku[a] != shozoku[b]:
            ans -= 1
            for k, v in shozoku.items():
                if v == shozoku[b]:
                    shozoku[k] = shozoku[a]
    elif a in shozoku:
        shozoku[b] = shozoku[a]
    elif b in shozoku:
        shozoku[a] = shozoku[b]

used = {}
for i in range(1, n+1):
    if i not in shozoku:
        ans += 1
print(ans)