Problem Statement in English

You’re given a graph with n nodes and m edges. Each edge has a weight of either 0 or 1. You have to find out how many edges you can add to the graph such that the graph remains an even weighted cycle.

Approach

Buckle up folks.

In order to detect cycles we’re going to have to have some point of reference to consider as the start of the cycle. Sounds like we need a root node.

We can use a union find data structure to keep track of the connected components of the graph.

But how do we keep track of the weights of the edges in the connected components? We assign the edge weights to the nodes instead of the edges.

We can do this by using a weight array that keeps track of the weight of the path from the node to its parent in the union find data structure.

The weight of the true root of the connected component is 0 - since it has no parent.

When we find the parent of a node named x, we also update the weight of x to be the weight of the path from x to its parent. This way, we can keep track of the weight from any node to its root.

When we add an edge, we check if the two nodes are in the same connected component. If they are, then we check if the weight of the edge is even or odd by XORing the weights of the two nodes and the weight of the edge.

If it’s even, then we can add it to the graph without creating an odd weighted cycle. If it’s odd, then we can’t add it to the graph because it would create an odd weighted cycle.

If the nodes are in different connected components, then we can add the edge to the graph and merge the two connected components. When we do this, one of the 2 roots becomes the parent of the other. Thus its weight stays the same, but the other root’s weight changes.

Let’s take a look at the formula to update the weight of a node whose parent changes during a find, and a union operation:

  • find: weight[x] ^= weight[parent[x]]
  • union: weight[pu] = w ^ weight[u] ^ weight[v]

The latter might look a bit confusing, but it makes sense when you understand how we arrived at it.

When we merge two connected components, we need to update the weight of the root of the merged component. Let’s say we merge pu into pv. The weight of pu is currently weight[pu], but after merging, we need to encode the relationship between pu and pv in the weight of pu:

w = weight[u] ^ weight[v]

But since u is the child of pu, and it’s merging with pv, and since pv becomes the parent of pu (since that’s the convention we’re using), we can rewrite the above formula as:

w = weight[u] ^ weight[pu] ^ weight[v]

Now if we XOR both sides with weight[u] and weight[v], we get:

w ^ weight[u] ^ weight[v] = weight[pu]

But why do we care about the weight of pu? Well, since pu is the child of pv, and it’s merging with pv, its weight needs to be updated!

And we’re done!

Solution in Python


class Solution:
    def numberOfEdgesAdded(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))
        weight = [0] * n
        
        def find(x):
            if parent[x] != x:
                root = find(parent[x])
                weight[x] ^= weight[parent[x]]
                parent[x] = root

            return parent[x]

        res = 0

        for u, v, w in edges:
            pu, pv = find(u), find(v)

            if pu == pv:
                # since we're trying to connect u and v with an edge of weight w, 
                # we need to check if the weight of the path from u to v 
                # is even or odd.
                if (weight[u] ^ weight[v] ^ w) == 0:
                    res += 1
            else:
                parent[pu] = pv
                # from the formula we derived above
                weight[pu] = w ^ weight[u] ^ weight[v]
                res += 1

        return res

Complexity

  • Time: $O(n + m)$
    Where n is the number of nodes and m is the number of edges.

  • Space: $O(n)$
    Since we store the parent and weight arrays.

Mistakes I Made

I had to look this up :(

And we are done.