Home > Software engineering >  Count pair of nodes that can't reach each other if you for each deleted edge
Count pair of nodes that can't reach each other if you for each deleted edge

Time:10-19

Question:

Given a undirected graph of N nodes and M edges. You need to solve 2 problems:

  • Problem 1: For each edge j (j : 1 -> M), if you delete that edge, count the number of nodes that can't reach each other (there's no path between that 2 nodes).
  • Problem 2: For each node i (i : 1 -> N), if you delete that node (which also deleted all of the edges connected to it), count the number of nodes that can't reach each other.

Example:

N = 6, M = 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4

(Edges are described as u - v)

Result:

  • For each edge j (j : 1 -> M): 0 0 0 9 0 0 0
  • For each node i (i : 1 -> N): 0 0 6 6 0 0

P/S: I have been thinking for many days but can't find a proper answer for this problem

CodePudding user response:

IF initial graph is connected, then the first problem is searching of bridges and the second one is searching of cut vertex / articulation points.

After revealing of bridge get sizes of connected components (there are two of them) and needed result is product of sizes (for example, components of size 2 and size 3 give 6 pairs)

After revealing of cut vertex number of components might be larger, and result is sum of pairwise products of sizes (for components with sizes 1,2,3 result is 1*2 1*3 2*3=11 pairs)

C code for solving both problems using DFS could be found here

  • Related