Strong Product Edge Count

Problem

Compute the number of edges in the strong product G1 x G2 of two undirected graphs.

The strong product combines the Cartesian and tensor products, so it has m1 * n2 + n1 * m2 + 2 * m1 * m2 edges. Return the count given the node counts and edge lists.

Hint

The three terms correspond to moving in the first factor, the second, or both.

Test cases

case 1

in: [2,[[0,1]],3,[[0,1],[1,2]]]

expected: 11

case 2

in: [1,[],2,[[0,1]]]

expected: 1

case 3

in: [2,[[0,1]],2,[]]

expected: 2

Starter codePython

def strong_product_edges(n1, edges1, n2, edges2):
    # Your code here
    pass

3 test cases · run your code against them in the editor