3887. Incremental Even-Weighted Cycle Queries

You are given a positive integer n.

There is an undirected graph with n nodes labeled from 0 to n - 1. Initially, the graph has no edges.

You are also given a 2D integer array edges, where edges[i] = [u_i, v_i, w_i] represents an edge between nodes u_i and v_i with weight w_i. The weight w_i is either 0 or 1.

Process the edges in edges in the given order. For each edge, add it to the graph only if, after adding it, the sum of the weights of the edges in every cycle in the resulting graph is even.

Return an integer denoting the number of edges that are successfully added to the graph.

long long uf[50505];
int cost[50505];
long long find(int u) {
     if (uf[u] == u) return u;
        int p = uf[u];
        uf[u] = find(p);
        cost[u] ^= cost[p];
        return uf[u];
}
bool uni(int u, int v, int c) {
    int pu = find(u), pv = find(v);
    int cu = cost[u], cv = cost[v];
    if(pu == pv) return !(cu ^ cv ^ c);
    uf[pv] = pu;
    cost[pv] = cu ^ cv ^ c;
    return true;
}
class Solution {
public:
    int numberOfEdgesAdded(int n, vector<vector<int>>& edges) {
        iota(begin(uf), end(uf),0);
        memset(cost, 0, sizeof cost);
        int res = 0;
        for(auto& e : edges) {
            if(uni(e[0],e[1],e[2])) res++;
        }
        return res;
    }
};