Problem Statement in English

You’re given an undirected graph with n nodes numbered from 1 to n and a 2D integer array edges where edges[i] = [u[i], v[i]] indicates that there is an edge between nodes u[i] and v[i].

Return the number of ways to assign weights of either 1 or 2 to the edges such that for every path from node 1 to the node with the maximum depth, the sum of the weights on the path is odd. Since the answer may be very large, return it modulo $10^9 + 7$.

Approach

There are 2 parts to this problem:

  1. Calculate the maximum depth of the graph.
  2. Calculate the number of ways to assign weights to the edges using the identity that the number

Calculating the max depth can be done using a BFS traversal of the graph. We can start from node 1 and keep track of the depth of each node as we traverse the graph. The maximum depth will be the maximum value of the depth encountered during the traversal.

To find the number of ways to assign odd weights to the edges we have to realise that we need an odd number of odd edges in the path from node 1 to the node with the maximum depth. This means that we can assign odd weights to any of the edges in the path, but we need to ensure that the total number of odd edges is odd. This can be calculated using the identity that the number of ways to assign weights to the edges is 2^(d-1) where d is the maximum depth of the graph.

And we’re done!

Solution in Python


class Solution:
    def assignEdgeWeights(self, edges: List[List[int]]) -> int:
        MOD = 10**9+7
        maxd = 0
        adj = defaultdict(list)

        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        q = deque([(1, 0)])
        seen = set([1])

        while q:
            node, d = q.popleft()

            seen.add(node)
            maxd = max(maxd, d)

            for nei in adj[node]:
                if nei not in seen:
                    q.append((nei, d + 1))
                    seen.add(nei)
            
        return pow(2, maxd - 1, MOD)

Complexity

  • Time: $O(n)$
    Since we are doing a BFS traversal of the graph, we will visit each node and edge at most once. Therefore, the time complexity is O(n), where n is the number of nodes in the graph.

  • Space: $O(n)$
    Since we are using a queue to perform the BFS traversal, we may need to store all the nodes in the worst case. Therefore, the space complexity is O(n), where n is the number of nodes in the graph.

Mistakes I Made

I didn’t use the identity for calculating the number of ways to assign edge weights, which is $2^{d-1}$ where d is the maximum depth of the graph. Instead, I tried to calculate the number of ways by iterating through the edges and counting the number of ways to assign weights for each edge, which led to a TLE.

And we are done.