ArticulationPoint identifies articulation points in a graph. It returns a boolean slice where each element indicates whether a vertex is an articulation point. Worst Case Time Complexity: O(|V| + |E|) Auxiliary Space: O(|V|) Reference: https://en.wikipedia.org/wiki/Biconnected_component and https://
(graph *Graph)
| 18 | // Auxiliary Space: O(|V|) |
| 19 | // Reference: https://en.wikipedia.org/wiki/Biconnected_component and https://cptalks.quora.com/Cut-Vertex-Articulation-point |
| 20 | func ArticulationPoint(graph *Graph) []bool { |
| 21 | // Time variable to keep track of the discovery time of a vertex |
| 22 | time := 0 |
| 23 | |
| 24 | // Initialize apHelper instance with the required data structures |
| 25 | apHelperInstance := &apHelper{ |
| 26 | isAP: make([]bool, graph.vertices), |
| 27 | visited: make([]bool, graph.vertices), |
| 28 | childCount: make([]int, graph.vertices), |
| 29 | discoveryTime: make([]int, graph.vertices), |
| 30 | earliestDiscovery: make([]int, graph.vertices), |
| 31 | } |
| 32 | |
| 33 | // Start traversal from the root (0) |
| 34 | articulationPointHelper(apHelperInstance, 0, -1, &time, graph) |
| 35 | |
| 36 | // Check if the root has only one child, making it non-articulate |
| 37 | if apHelperInstance.childCount[0] == 1 { |
| 38 | apHelperInstance.isAP[0] = false |
| 39 | } |
| 40 | |
| 41 | return apHelperInstance.isAP |
| 42 | } |
| 43 | |
| 44 | // articulationPointHelper recursively traverses the graph using DFS and marks articulation points. |
| 45 | // It updates `childCount`, `discoveryTime`, and `earliestDiscovery` slices for the given vertex. |