Connected Components in an Undirected Graph: the idea to remember.

The core insight

Start a traversal from each unvisited vertex and increment the component count once per traversal.

Why it works

A traversal reaches exactly one component. Every vertex is visited by the traversal of its component and by no other traversal.

The mistake to avoid

Include vertices with no edges. Mark at push time so duplicates do not accumulate in the stack.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int countComponents(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) { graph.get(e[0]).add(e[1]); graph.get(e[1]).add(e[0]); }
    boolean[] seen = new boolean[n]; int count = 0;
    for (int i = 0; i < n; i++) if (!seen[i]) {
        count++; Deque<Integer> stack = new ArrayDeque<>(); stack.push(i); seen[i] = true;
        while (!stack.isEmpty()) for (int next : graph.get(stack.pop())) if (!seen[next]) {
            seen[next] = true; stack.push(next);
        }
    }
    return count;
}

Make the next connection