Connected Components in an Undirected Graph
Determine the number of connected components in an undirected graph.
Input: n = 4, edges = [[0,1],[2,3]]
Output: 2
Explanation: The graph is split completely evenly into two distinct isolated components: nodes {0,1} and nodes {2,3}.

Question

Connected Components in an Undirected Graph

Determine the number of connected components in an undirected graph.

Input: n = 4, edges = [[0,1],[2,3]]

Output: 2

Explanation: The graph is split completely evenly into two distinct isolated components: nodes {0,1} and nodes {2,3}.

Anonymous · Accepted Answer

public static int connectedComps(int n, int[][] edges) { int connectedComps = -1; HashMap> graph = new HashMap<>(); for(int[] edge: edges) { int u = edge[0]; int v = edge[1]; graph.computeIfAbsent(u, value->new ArrayList()).add(v); graph.computeIfAbsent(v, value->new ArrayList()).add(u); } boolean[] visited = new boolean[n]; for(int i=0;i> graph, int src, boolean[] vis) { vis[src] = true; for(Integer neighbor:graph.get(src)) { if(!vis[neighbor]) { dfsConnected(n, graph, neighbor, vis); } } }

Connected Components in an Undirected Graph

Practice this question with AI

Go Premium

Community Answers

Unlock Full Access

Practice More Questions