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):
#include <bits/stdc++.h>
using namespace std;
//unionfind
typedef pair<int, int> P;
const int MAX_N = 100010;
int m, n;
int par[MAX_N];    //親
int deapth[MAX_N]; //木の深さ
int cnt[MAX_N];
int num;

vector<int> vec[MAX_N];
//n要素で初期化
void init(int n)
{
    for (int i = 0; i < n; i++)
    {
        par[i] = i;
        deapth[i] = 0;
        cnt[i] = 1;
    }
}
//木の根を求める
int find(int x)
{
    if (par[x] == x)
    {
        return x;
    }
    else
    {
        return par[x] = find(par[x]);
    }
}

//xとyの属する集合を併合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (deapth[x] < deapth[y])
    {
        par[x] = y;
        cnt[y] += cnt[x];
    }
    else
    {
        par[y] = x;
        cnt[x] += cnt[y];
        if (deapth[x] == deapth[y])
            deapth[x]++;
    }
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

int main()
{
    cin >> n >> m;
    init(MAX_N);
    vector<P> v;
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        if (z % 2 == 0)
        {
            unite(x, y);
        }
        else
        {
            v.push_back(P(x, y));
            v.push_back(P(y, x));
        }
    }
    for (int i = 0; i < v.size(); i++)
    {
        vec[find(v[i].first)].push_back(find(v[i].second));
    }
    vector<bool> fl(n + 1, false);
    vector<P> u;

    for (int i = 1; i <= n; i++)
    {
        if (fl[find(i)])
            continue;
        fl[find(i)] = true;
        u.push_back(P(cnt[find(i)], find(i)));
    }

    sort(u.begin(), u.end(), greater<P>());

    vector<bool> f(n + 1, false);
    int ans = 0;
    for (int i = 0; i < u.size(); i++)
    {
        if (f[find(u[i].second)])
            continue;
        ans++;
        f[u[i].second] = true;
        for (int i = 0; i < vec[u[i].second].size(); i++)
        {
            int x = vec[u[i].second][i];
            f[find(x)] = true;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!f[find(i)])
            ans++;
    }
    cout << ans << endl;
}


import collections
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    def find(self, x):
        deque = collections.deque()
        t = x
        while t != self.parent[t]:
            deque.append(t)
            t = self.parent[t]
        while deque:
            tmp = deque.pop()
            self.parent[tmp] = t
        return t
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.depth[x] < self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x] += self.cnt[y]
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return self.cnt[self.find(x)]
n, m = map(int, input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x, y, z = map(int, input().split())
    utree.unite(x, y)
s = {utree.find(i) for i in range(1, n+1)}
print(len(s))

Verdicts: Runtime Error

Accepted