ConnectedComponents.java

amitsen01ei

Oct 16th, 2023 (edited)

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

Java 1.40 KB | Source Code | 0 0

raw download clone embed print report

public class ConnectedComponents {
/**
* Returns the number of connected components in the graph.
*
* Time complexity: O(A + B) where A is the number of nodes and B is the number of edges.
* Space complexity: O(A + B) for storing the graph and visited set.
*
* @param A Number of nodes in the graph.
* @param B 2D array representing the edges of the graph.
* @return Number of connected components.
*/
public int solve(int A, int[][] B) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 1; i <= A; i++) {
graph.put(i, new ArrayList<>());
}
for (int[] edge : B) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
// Set to keep track of visited nodes.
Set<Integer> visited = new HashSet<>();
int components = 0;
for (int i = 1; i <= A; i++) {
if (!visited.contains(i)) {
dfs(i, graph, visited);
components++;
}
}
return components;
}
private static void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
if (visited.contains(node)) return;
visited.add(node);
for (int neighbor : graph.get(node)) {
dfs(neighbor, graph, visited);
}
}
}

Add Comment

Please, Sign In to add comment