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