Incremental Even-Weighted Cycle Queries - Solution & Explanation

Problem Overview: You process graph queries where edges are added incrementally. After each insertion, determine whether the new edge forms a cycle whose total weight is even. The challenge is answering these checks efficiently without recomputing paths for every query.

Approach 1: Recompute Cycle Using DFS/BFS (Brute Force) (Time: O(Q * (V + E)), Space: O(V + E))

For each query, temporarily add the edge and search for an existing path between the two endpoints using DFS or BFS. While traversing, accumulate the path weight parity (even or odd). If a path already exists and the combined parity with the new edge results in an even total, the edge closes an even-weighted cycle. This method repeatedly scans the graph, so performance degrades quickly when the number of queries grows. It works for small graphs or when queries are limited.

Approach 2: Maintain Prefix Parity with Graph Traversal (Time: O(V + E) preprocessing + O(path length) per query, Space: O(V))

Store parity information for paths relative to a chosen root using a traversal such as BFS. When a query connects two nodes, compare their stored parity values and combine with the edge weight parity to determine the resulting cycle parity. The issue is maintaining correctness after many incremental insertions, since new edges can invalidate previously computed parity paths. This technique works only if the graph structure remains mostly static.

Approach 3: Disjoint Set Union with Parity Tracking (Optimal) (Time: O((N + Q) α(N)), Space: O(N))

Use a Union-Find (Disjoint Set Union) structure where each node stores the parity of the path to its parent. During find(), path compression updates parity relative to the root. When inserting an edge (u, v, w), check whether both nodes already share the same root. If they do, the parity difference between u and v combined with the new edge weight reveals whether the formed cycle has even weight. If the roots differ, merge them while preserving parity constraints. This approach processes queries almost in constant time due to the inverse Ackermann factor.

Parity handling is essentially an XOR operation on weight mod 2. The DSU maintains the parity from each node to its root, so the parity between any two nodes can be derived quickly. This pattern also appears in problems involving bipartite constraints and XOR relationships, commonly implemented with graph reasoning and disjoint set union structures.

Recommended for interviews: Start by describing the brute-force path search to show you understand the cycle detection requirement. Then move to DSU with parity tracking. Interviewers expect the union-find optimization because it handles incremental connectivity queries efficiently while maintaining parity constraints.