Created
March 30, 2020 20:54
-
-
Save FANHOOOO/55d9881cdf00a7dec4189bd70047392b to your computer and use it in GitHub Desktop.
Critical Node
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.ArrayList; | |
| import java.util.Arrays; | |
| import java.util.Collections; | |
| import java.util.HashMap; | |
| import java.util.HashSet; | |
| import java.util.List; | |
| import java.util.Map; | |
| import java.util.Set; | |
| import java.util.stream.IntStream; | |
| public class CriticalRouters { | |
| /** | |
| * You are given an undirected connected graph. | |
| * An articulation point (or cut vertex) is defined as a vertex which, | |
| * when removed along with associated edges, makes the graph disconnected | |
| * (or more precisely, increases the number of connected components in the graph). | |
| * The task is to find all articulation points in the given graph. | |
| * | |
| * Input: | |
| * The input to the function/method consists of three arguments: | |
| * | |
| * numNodes, an integer representing the number of nodes in the graph. | |
| * numEdges, an integer representing the number of edges in the graph. | |
| * edges, the list of pair of integers - A, B representing an edge between the nodes A and B. | |
| * Output: | |
| * Return a list of integers representing the critical nodes. | |
| * | |
| * Example: | |
| * | |
| * Input: numNodes = 7, numEdges = 7, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3, 4]] | |
| * | |
| * | |
| * Output: [2, 3, 5] | |
| * | |
| */ | |
| /** | |
| * Time complexity: number of nodes: N, number of edges: E | |
| * O(N + E), we goes through each node and each edge | |
| * Space complexity: O(N * M) M is the maximum edges size of each node | |
| * Tarjan's Algorithm | |
| */ | |
| private int id; | |
| public List<Integer> getCriticalPoints(int numNodes, int numEdges, int[][] edges) { | |
| if (numNodes < 1) { | |
| return Collections.emptyList(); | |
| } | |
| Map<Integer, Set<Integer>> map = new HashMap<>(); | |
| IntStream.range(0, numNodes).forEach(i -> map.put(i, new HashSet<>())); | |
| for (int[] edge : edges) { | |
| map.get(edge[0]).add(edge[1]); | |
| map.get(edge[1]).add(edge[0]); | |
| } | |
| int[] lowIds = new int[numNodes]; | |
| int[] ids = new int[numNodes]; | |
| int[] parents = new int[numNodes]; | |
| Arrays.fill(ids, -1); | |
| Arrays.fill(parents, -1); | |
| Set<Integer> result = new HashSet<>(); | |
| id = 0; | |
| dfs(map, lowIds, ids, parents, 0,result); | |
| return new ArrayList<>(result); | |
| } | |
| private void dfs(Map<Integer, Set<Integer>> map, int[] lowIds, int[] ids, int[] parents, int node, Set<Integer> result) { | |
| int childrenCount = 0; | |
| ids[node] = lowIds[node] = id++; | |
| System.out.println(String.format("Current Node: %d, Node Id: %d.......", node, ids[node])); | |
| for (int neighbor : map.get(node)) { | |
| if (ids[neighbor] == -1) { | |
| childrenCount++; | |
| parents[neighbor] = node; | |
| System.out.println(String.format("DFS from Node %d dfs to Neighbor %d", node, neighbor)); | |
| dfs(map, lowIds, ids, parents, neighbor, result); | |
| lowIds[node] = Math.min(lowIds[node], lowIds[neighbor]); | |
| System.out.println(String.format("Update LowId of Node %d to %d", node, lowIds[node])); | |
| if ((parents[node] == -1 && childrenCount > 1) || (parents[node] != -1 && lowIds[neighbor] >= ids[node])) { | |
| result.add(node); | |
| System.out.println(String.format("Node %d is Articulation Point", node)); | |
| } | |
| // (parents[node] == -1 && childrenCount > 1) is for the case of cycle 0 -> 1 -> 2 -> 0 | |
| } else if (neighbor != parents[node]) { | |
| lowIds[node] = Math.min(lowIds[node], lowIds[neighbor]); | |
| System.out.println(String.format("Update LowId of Node %d to %d", node, lowIds[node])); | |
| } | |
| } | |
| } | |
| public static void main(String[] args) { | |
| CriticalRouters ins = new CriticalRouters(); | |
| int[][] edges = { | |
| {0, 1}, | |
| {0, 2}, | |
| {1, 3}, | |
| {2, 3}, | |
| {2, 5}, | |
| {5, 6}, | |
| {3, 4} | |
| }; | |
| System.out.println(ins.getCriticalPoints(7, 7, edges)); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment