TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
N,M=map(int, input().split())

outgoing=dict()
incoming=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in outgoing: outgoing[x].add(y)
  else: outgoing[x]={y}
  if y in incoming: incoming[y].add(x)
  else: incoming[y]={x}
#print(outgoing)
#print(incoming)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    
cnt=0
for i in range(1, N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

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

outgoing=dict()
incoming=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in outgoing: outgoing[x].add(y)
  else: outgoing[x]={y}
  if y in incoming: incoming[y].add(x)
  else: incoming[y]={x}
#print(outgoing)
#print(incoming)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    """
    if v in outgoing:
      for u in outgoing[v]: dfs(u)
    """
    if v in incoming:
      for u in incoming[v]: dfs(u)
cnt=0
for i in range(1, N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

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

outgoing=dict()
incoming=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in outgoing: outgoing[x].add(y)
  else: outgoing[x]={y}
  if y in incoming: incoming[y].add(x)
  else: incoming[y]={x}
#print(outgoing)
#print(incoming)
"""
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    if v in outgoing:
      for u in outgoing[v]: dfs(u)
    if v in incoming:
      for u in incoming[v]: dfs(u)

cnt=0
for i in range(1, N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)
"""

import sys
mod = 10**9+7
sys.setrecursionlimit(mod)
N,M=map(int, input().split())

adj={i: set() for i in range(1,N+1)}
for i in range(M):
  x,y,z=map(int, input().split())
  adj[x].add(y)
  adj[y].add(x)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    for u in adj[v]: dfs(u)
cnt=0
for i in range(1,N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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))

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+1):
    tank.add(uf.find(i))
print(len(tank))

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
class UnionFind:
    def __init__(self, n):
        self.table = [-1 for _ in range(n)]

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

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1<=d2:
            self.table[r2] = r1
            if d1==d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2

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

ans = 0
for v in uf.table:
    if v<0:
        ans += 1
print(ans)

class UnionFind:
    def __init__(self, n):
        self.table = [-1 for _ in range(n)]

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

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1<=d2:
            self.table[r2] = r1
            if d1==d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2

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.union(x, y)

ans = 0
for v in uf.table:
    if v<0:
        ans += 1
print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
#!/usr/bin/env python3

import numpy as np


# Python 3 modules: https://docs.python.org/3/library/

import sys
import math, itertools, operator
from math import *
from math import factorial as fact
from itertools import permutations, combinations
from functools import reduce
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5
from fractions import gcd

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(inp = input, sep = ' ', conv = int):
    return map(conv, inp().split(sep = sep))

################################################################################

sys.setrecursionlimit(20000)

N, M = input_ints()

# D[i][j]: Card i has a rel. with card j
D = [[] for i in range(N)]
for i in range(M):
    x, y, z = input_ints()
    x -= 1
    y -= 1
    D[x].append(y)

L = [len(x) for x in D]
Lvalid = N - L.count(0)
Ldone = 0
known = [False for i in range(N)]
done = 0
cost = 0

def magic(n):
    global done, known, L, D, Ldone
    for idx in D[n]:
        if not known[idx]:
            known[idx] = True
            done += 1
            L[idx] = -1
            Ldone += 1
            magic(idx)

#print(L)
#print(list(reversed(np.argsort(L))))
while done < N:
    n = np.argmax(L)
    done += 1
    Ldone += 1
    #if Ldone == Lvalid:
    if L[n] == 0:
        cost += N - Lvalid - 1
        break
    L[n] = -1
    cost += 1
    known[n] = 1
    magic(n)

print(cost)


#!/usr/bin/env python3

import sys

sys.setrecursionlimit(1000000)

N, M = [int(x) for x in input().split()]

# D[i][j]: Card i has a rel. with card j
D = [[] for i in range(N)]
for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    D[x].append(y)
    D[y].append(x)

visited = [False for i in range(N)]
def dfs(n):
    for idx in D[n]:
        if not visited[idx]:
            visited[idx] = True
            dfs(idx)

cnt = 0
for n in range(N):
    if not visited[n]:
        visited[n] = True
        dfs(n)
        cnt += 1
print(cnt)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
N, M = (int(x) for x in input().split())

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


magic_act_num = 0

known = [False for x in range(N)]
judge = 0
index = 0
for x, y, _ in xyz:
    x = x-1
    y = y-1
    if known[x] and known[y]:
        continue;

    
    if known[x]:
        if known[y] is False:
            known[y] = True
            judge += 1
    else:
        if known[y]:
            known[x] = True
            judge += 1
        else:
            known[x] = True
            known[y] = True
            judge += 2
            magic_act_num += 1
    i = 0
    for a, b, _ in xyz:
        if i <= index:
            continue
        a = a - 1;
        b = b - 1;
        if known[a] is x and known[b] is y:
            continue
        if known[a] is y and known[b] is x:
            continue
        if known[a] is x:
            if known[b] is not y:
                known[b] = True
        if known[a] is y:
            if known[b] is not x:
                known[b] = True
        if known[b] is x:
            if known[a] is not y:
                known[a] = True
        if known[b] is y:
            if known[a] is not x:
                known[a] = True
        i++
    index++

magic_act_num += (N-judge)

print(magic_act_num)


import sys
sys.setrecursionlimit(100000)

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

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

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

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

    print(len(rlist))

if __name__ == '__main__':
    main()


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
a = input().split()
N = int(a[0])
M = int(a[1])

l = []
f = []
for i in range(N):
	temp = []
	l.append(temp)
	f.append(0)

for i in range(M):
	b = input().split()
	X = int(b[0]) - 1
	Y = int(b[1]) - 1
	l[X].append(Y)
	l[Y].append(X)

def search(cnt, li, flag, num):
	if(flag[num] == 0):
		flag[num] = cnt
		if(len(li[num]) != 0):
			for i in range(len(li[num])):
				search(cnt, li, flag, li[num][i])
		
cnt = 0
for i in range(N):
	print(f)
	if(f[i] == 0):
		cnt += 1
		search(cnt, l, f, i)			
print(cnt)

import sys
sys.setrecursionlimit(1000000)

a = input().split()
N = int(a[0])
M = int(a[1])

l = []
f = []
for i in range(N):
	temp = []
	l.append(temp)
	f.append(0)

for i in range(M):
	b = input().split()
	X = int(b[0]) - 1
	Y = int(b[1]) - 1
	l[X].append(Y)
	l[Y].append(X)

def search(cnt, li, flag, num):
	if(flag[num] == 0):
		flag[num] = cnt
		if(len(li[num]) != 0):
			for i in range(len(li[num])):
				search(cnt, li, flag, li[num][i])
		
cnt = 0
for i in range(N):
	if(f[i] == 0):
		cnt += 1
		search(cnt, l, f, i)			
print(cnt)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
n, m = map(int, input().split())
w = [list(map(int, input().split())) for i in range(m)]
print(w)
a = [0 for i in range(n)]
if w[0][2] % 2 == 0:
        a[w[0][0]-1] = 1
        a[w[0][1]-1] = 1
else:
        a[w[0][0]-1] = 1
        a[w[0][1]-1] = 2
magic = 1
for i in range(2,m+1):
    if w[i-1][2] % 2 == 0:
        if a[w[i-1][0]-1] == 0 and a[w[i-1][1]-1] == 0:
            a[w[i-1][0]-1] = 1
            a[w[i-1][1]-1] = 1
            magic += 1
        elif a[w[i-1][0]-1] == 0:
            a[w[i-1][0]-1] = a[w[i-1][1]-1]
        elif a[w[i-1][1]-1] == 0:
            a[w[i-1][1]-1] = a[w[i-1][0]-1]
    else:
        if a[w[i-1][0]-1] == 0 and a[w[i-1][1]-1] == 0:
            a[w[i-1][0]-1] = 1
            a[w[i-1][1]-1] = 2
            magic += 1
        elif a[w[i-1][0]-1] == 0:
            a[w[i-1][0]-1] = a[w[i-1][1]-1] % 2 + 1
        elif a[w[i-1][1]-1] == 0:
            a[w[i-1][1]-1] = a[w[i-1][0]-1] % 2 + 1
for i in range(n):
    if a[i] == 0:
        magic += 1
    else:
        continue
print(magic)

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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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


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

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

print(uf.group_count())

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()


def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a


def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    
    A[by] = bx

V = [i for i in range(N)]
for i in range(M):
    x, y, z = lr()
    if find(V, x-1) != find(V, y-1):
        union(V, x-1, y-1)

answer = [find(x) for x in set(V)]
print(len(set(answer)))
# 36


import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()


def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a


def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    
    A[by] = bx

V = [i for i in range(N)]
for i in range(M):
    x, y, z = lr()
    if find(V, x-1) != find(V, y-1):
        union(V, x-1, y-1)

answer = [find(x) for x in set(V)]
print(len(answer))
# 36


# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


def find(A,x):
    p = A[x]
    if p == x: return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[by] = bx 

N, M = lr()
V = [x for x in range(N+1)]
for _ in range(M):
    x, y, z = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)

V = [find(V, x) for x in V]
s = set(V[1:])
answer = len(s)
print(answer)
# 55


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

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

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

print(par.count(-1))

import sys
sys.setrecursionlimit(1000000)

class UnionFind:
	def __init__(self, n=1):
		self.par = [ i for i in range(n)]
		self.size = [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 merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)

class UnionFold:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        
        
        self.rank = [0]*(n+1)
        
    def find(self, x):
        
        if self.par[x]==x:
            return x
        
        
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
    
    
    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    
    def union(self,x,y):
        
        x = self.find(x)
        y = self.find(y)
        
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                
def main():
    N,M = map(int, input().split())
    union_fold = UnionFold(N)
    for _ in range(M):
        x,y,z = map(int, input().split())
        if not(union_fold.same(x,y)):
            union_fold.union(x,y)
    
    n=0
    for i in range(1,N+1):
        if union_fold.par[i]==i:
            n+=1
    print(n)
    
main()

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n,m=map(int,input().split())
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
u=UnionFind(n)
for i in range(m):
  a,b,c=map(int,input().split())
  u.merge(a-1,b-1)
a=[0]*n
for i in range(n):
  a[i]=u.root(i)
print(len(a))


n,m = map(int,input().split())
a = []
for i in range(n):
  b,c,d = map(int,input().split())
  if b in a and c in a:
    m = m-1
  a.append(b)
  a.append(c)
print(n-m)

import sys
sys.setrecursionlimit(100000)
n,m=map(int,input().split())
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
u=UnionFind(n)
for i in range(m):
  a,b,c=map(int,input().split())
  if a>b:
    a=g
    g=b
    b=a
  u.merge(a-1,b-1)
a=[0]*n
for i in range(n):
  a[i]=u.root(i)
print(len(set(a)))


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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)

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[v] == -1:
        renketu_list[v] = count
        while len(g[v])>0:
          stack.append(g[v].pop())

print(count)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from collections import deque

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

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

for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    

seen=[False]*(N+1)


count=0

for i in range(1,N+1):
    if seen[i]==False:
        seen[i]=True
        S=deque([i])
        
        while S:
            v=S.popleft()
            
            for i in graph[v]:
                if seen[i]==False:
                    seen[i]=True
                    S.append(i)
        count+=1

print(count)

from collections import deque
N,M=list(map(int,input().split()))
even_list=[list(map(int,input().split())) for _ in range(M)]

    

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):
    
    S=deque([s])
    C=set()
    
    while S:
        v=S.pop()
        seen[v]=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

from collections import deque
N,M=list(map(int,input().split()))
even_list=[list(map(int,input().split())) for _ in range(M)]

    

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):
    
    S=deque([s])
    C=set()
    
    while S:
        v=S.pop()
        seen[v]=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)

from collections import deque


N,M=list(map(int,input().split()))
graph=[[] for _ in range(N+1)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    

seen=[False]*(N+1)


count=0

for i in range(1,N+1):
    if seen[i]==False:
        seen[i]=True
        S=deque([i])
        
        while S:
            v=S.popleft()
            
            for i in graph[v]:
                if seen[i]==False:
                    seen[i]=True
                    S.append(i)
        count+=1

print(count)

Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np
from scipy.sparse.csgraph import connected_components
N, M = map(int, input().split())
matrix = np.array([[0] * N for _ in range(N)], dtype=np.bool)
for _ in range(M):
    i, j, _ = map(int, input().split())
    matrix[i - 1][j - 1] = True

print(connected_components(matrix)[0])


import numpy as np
from scipy.sparse import csr_matrix, csgraph
N, M = map(int, input().split())
print(csgraph.connected_components(csr_matrix(([1] * M, (np.array([tuple(map(lambda n: int(n) - 1, input().split()[:2])) for _ in range(M)], dtype=np.int32).T)), shape=(N, N), dtype=np.int32), return_labels=False))


Verdicts: Time Limit Exceeded

Accepted
Problem: 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.

Submission attempts (in order):
import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    global gone
    stack = [v]
    gone[v] = True
    while stack:
        v = stack.pop()
        for w in graph[v]:
            gone[w] = True
            stack.append(w)

n,m = map(int,input().split())
exist = [False for i in range(n+1)]
gone = [False for i in range(n+1)]
graph = [[] for _ in range(n+1)]
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
    exist[x] = True
    exist[y] = True
ans = 0

for i in range(1,n+1):
    if exist[i] == True:
        if gone[i] == False:
            dfs(i)
            ans += 1
    else:
        ans += 1

print(ans)

import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    global gone
    stack = [v]
    gone[v] = True
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if gone[w] == False:
                stack.append(w)
            gone[w] = True

n,m = map(int,input().split())
exist = [False for i in range(n+1)]
gone = [False for i in range(n+1)]
graph = [[] for _ in range(n+1)]
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
    exist[x] = True
    exist[y] = True
ans = 0

for i in range(1,n+1):
    if exist[i] == True:
        if gone[i] == False:
            dfs(i)
            ans += 1
    else:
        ans += 1

print(ans)

Verdicts: Time Limit Exceeded

Accepted
Problem: 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.

Submission attempts (in order):
N, M =map(int,input().split())
class UnionFind(object):
    def __init__(self, n=1):
        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]:
                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 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]
uf = UnionFind(N)
cnt = 0
for i in range(M):
  x, y, z = map(int, input().split())
  if !uf.is_same(x, y):
    cnt += 1
    uf.union(x,y)
    
print(N-cnt)

N, M =map(int,input().split())
class UnionFind(object):
    def __init__(self, n=1):
        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]:
                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 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]
uf = UnionFind(N)
cnt = 0
for i in range(M):
  x, y, z = map(int, input().split())
  if not uf.is_same(x-1, y-1):
    cnt += 1
    uf.union(x-1,y-1)
    
print(N-cnt)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

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

for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

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

for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)
print(res)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)

n, m = map(int, input().split())
adj = [[] for _ in range(m)]
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)

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[i]:
    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)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from collections import deque
n = int(input())
q = deque(maxlen=n-1)

for i in range(n - 1):
    a, b, c = map(int, input().split())
    q.append([a-1, b-1, c % 2])

cllist = [-1] * n
a, b, c = q.popleft()
cllist[a] = 0
cllist[b] = c
while q:
    a, b, c = q.popleft()
    if cllist[a] != -1:
        cllist[b] = (cllist[a] + c) % 2
    elif cllist[b] != -1:
        cllist[a] = (cllist[b] + c) % 2
    else:
        q.append([a, b, c])
print(*cllist)


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

p = list(range(n))


def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


def union(x, y):
    x, y = find(x), find(y)
    p[x] = p[y] = min(x, y)


for _ in range(m):
    x, y, z = [int(i) - 1 for i in input().split()]
    if find(x) != find(y):
        union(x, y)

ans = set()
for i in range(n):
    find(i)
print(len(set(p)))


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.total = 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 same_check(self, x, y):
        return self.find[x] == self.find[y]
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x-1, y-1)
print(union.total)


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.total = 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 same_check(self, x, y):
        return self.find(x) == self.find(y)
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x-1, y-1)
print(union.total)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import sys
sys.setrecursionlimit(10 ** 5)

input = sys.stdin.readline()

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

ans = list(range(N))
def root(a):
    if a==ans[a]:
        return a
    else:
        return root(ans[a])

for _ in range(M):
    x, y, _ = map(lambda a: int(a)-1, input().split())
    if root(x) != root(y):
        rx = root(x)
        ry = root(y)
        while y != ry:
            ans[y], y = rx, ans[y]
        ans[ry] = rx

A = {}
for a in ans:
    A[a] = 1

print(len(A))


import sys
sys.setrecursionlimit(10 ** 5)

input = sys.stdin.readline

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

ans = list(range(N))
def root(a):
    if a==ans[a]:
        return a
    else:
        ans[a] = root(ans[a]) 
        return ans[a]

for _ in range(M):
    x, y, _ = map(lambda a: int(a)-1, input().split())
    rx, ry = root(x), root(y)
    if rx != ry:
        ans[ry] = rx

count = 0
for i,a in enumerate(ans):
    count += i==a


print(count)


Verdicts: Runtime Error

Accepted