Loose Pieces on the Table

Easyunion-findAlso known as Number of Connected Components in an Undirected Graph

Your little brother tipped out a box of building bricks numbered 0 to n - 1 and spent the afternoon snapping them together. He kept a log: each line says which two bricks he snapped together, like [2, 5].

Before tidying up, you want to know how many separate pieces are lying on the table. A piece is any group of bricks held together, directly or through other bricks. A brick nobody touched is a piece on its own.

Your task

Write countPieces(n, snaps). There are n bricks, numbered 0 to n - 1. Each entry [a, b] in snaps means bricks a and b were snapped together. Return the number of separate pieces.

The same pair can appear more than once, and snaps can close loops (for example 0-1, 1-2, 2-0). Neither changes which bricks are joined.

countPieces(n: int, snaps: int[][]) → int

Examples

Example 1

Input

n = 6
snaps = [[0, 1], [1, 2], [4, 5]]

Output

Why

Bricks 0, 1 and 2 form one piece (0 is joined to 2 through 1). Bricks 4 and 5 form a second. Brick 3 was never touched, so it is a third piece.

Example 2

Input

n = 4
snaps = [[0, 1], [1, 2], [2, 0], [0, 1]]

Output

Why

Four snaps, but the last two add nothing new: 2-0 closes a loop and 0-1 repeats. Bricks 0, 1, 2 are one piece and brick 3 is another, so 2. Computing 4 bricks minus 4 snaps = 0 would be wrong.

Constraints

1 ≤ n ≤ 2,000
0 ≤ snaps.length ≤ 5,000
0 ≤ a, b < n and a ≠ b

Start with brute force

For each snap, relabel: give every brick in the second brick's piece the first brick's label by scanning all n bricks. Count the distinct labels at the end.

That is n work per snap, so 5,000 snaps × 2,000 bricks = 10 million steps. It works, but union-find does each snap in nearly constant time. Building the full adjacency list and running a depth-first search from each unvisited brick is also fast and perfectly fine here.

Hints

0 of 4 shown

Hint 1
Start with every brick as its own piece, so there are n pieces. When you process the snap [0, 1] in the first example, how does the count change? When does a snap not change it?
Hint 2
A snap lowers the count by one exactly when its two bricks were in different pieces before it. If they were already in the same piece, it changes nothing.
Hint 3
So you need a fast way to ask "are these two bricks already in the same piece?" and to merge two pieces. Give every piece one brick that acts as its leader.
Hint 4
Use union-find. Keep parent[i], starting as i. find(x) follows parents up to the leader. For each snap, find both leaders; if they differ, point one at the other and subtract one from the count. Shortening the paths as find walks them keeps it fast.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Start by assuming every brick is alone: n pieces. Each snap either joins two different pieces, which lowers the count by one, or joins two bricks that were already connected, which changes nothing. Union-find answers "already connected?" quickly by giving each piece a leader.

Trace the second example, n = 4 with snaps 0-1, 1-2, 2-0, 0-1. At the start, parent = [0, 1, 2, 3] and pieces = 4.

Snap 0-1. Leaders are 0 and 1, different. Set parent[0] = 1. Pieces = 3.
Snap 1-2. Leaders are 1 and 2, different. Set parent[1] = 2. Pieces = 2.
Snap 2-0. find(2) is 2. find(0) walks 0 → 1 → 2, so its leader is also 2. Same piece: skip.
Snap 0-1. Both leaders are 2. Skip.

Answer: 2. Brick 3 was its own leader the whole time.

The line parent[x] = parent[parent[x]] makes each brick on the walk skip one level up. Over many calls the trees stay very flat, so find stays very fast.

Reference solution

function countPieces(n, snaps) {
  const parent = Array.from({ length: n }, (_, i) => i);
  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // shorten the path as we go
      x = parent[x];
    }
    return x;
  }
  let pieces = n;
  for (const [a, b] of snaps) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) {
      parent[ra] = rb; // merge two different pieces
      pieces--;
    }
  }
  return pieces;
}

def count_pieces(n, snaps):
    parent = list(range(n))
 
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # shorten the path as we go
            x = parent[x]
        return x
 
    pieces = n
    for a, b in snaps:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb  # merge two different pieces
            pieces -= 1
    return pieces

TimeO(n + m log n)m snaps, each doing two finds. Path shortening keeps each find at O(log n) amortized, and in practice the trees are so flat it is close to constant. Adding union by size brings it to almost exactly constant.

SpaceO(n)One parent entry per brick.

Learn the idea: Union-Find Depth-First Search Graph Basics

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code