Firewall Edge Cut Value

Problem

Count the firewall edges that run between a protected set and the rest of an undirected graph.

An edge counts when exactly one endpoint is protected. protected is a list of node indices and edges is a list of [u, v] pairs. Return the integer count.

Hint

Firewalling a node set pays for every connection that leaves it.

Test cases

case 1

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

expected: 3

case 2

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

expected: 0

case 3

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

expected: 0

case 4

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

expected: 2

Starter codePython

def firewall_cut(n, edges, protected):
    # Your code here
    pass

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