Collapse every SCC into a single node and build the condensation graph, where each edge represents a connection between two different SCCs. Return the number of unique edges in that DAG. Pattern focus: Strongly Connected Components. This is a graph-compression application of SCC decomposition.
n = number of vertices, edges = directed edges [u, v]
number of unique edges in the condensation DAG
Example 1:
Input:
n = 5 edges = [[1,2],[2,1],[2,3],[3,4],[4,3],[4,5]]
Output:
2
Explanation:
The SCCs are {1,2}, {3,4}, and {5}, with two unique condensation edges.
Example 2:
Input:
n = 4 edges = [[1,2],[2,3],[3,1],[3,4]]
Output:
1
Explanation:
Only one unique edge appears between SCCs.
Example 3:
Input:
n = 3 edges = [[1,2],[2,1],[2,3],[3,2]]
Output:
0
Explanation:
All vertices are in one SCC, so the condensation DAG has no edges.