Loading page…
Practice problem · easy
You work on the monitoring page of a data centre. There are n servers, numbered 0 to n - 1. Every minute the page checks the cables between them. A cable that passed its last health check is listed as a link between two servers.
Servers that can reach each other, directly or through other servers, form one piece of the network. Your team lead says: "If the network is in more than one piece, page the on-call engineer. Tell me how many pieces there are."
Write count_pieces(n, links).
n is the number of servers.links[i] = [a, b] means a working cable joins servers a and b. It works in both directions.1 means the network is still in one piece.A server with no working cable is a piece of its own. The same cable can be listed more than once.
Input: n = 6, links = [[0, 1], [1, 2], [3, 4]]
Output: 3Start with 6 pieces, one for each server. Each link that joins two different pieces lowers the count by 1.
| Link | Pieces joined? | Pieces left |
|---|---|---|
| start | 6 | |
| [0, 1] | yes: 0 and 1 are apart | 5 |
| [1, 2] | yes: 2 is apart from {0, 1} | 4 |
| [3, 4] | yes: 3 and 4 are apart | 3 |
The pieces are {0, 1, 2}, {3, 4} and {5}. The answer is 3.
Input: n = 4, links = [[0, 1], [1, 2], [2, 3]]
Output: 1The links make a chain through every server, so there is one piece.
Input: n = 3, links = []
Output: 3With no working cable, every server is alone: 3 pieces.
1 ≤ n ≤ 100,0000 ≤ len(links) ≤ 200,000, and every row is [a, b] with 0 ≤ a, b < n and a ≠ bThere can be 100,000 servers and 200,000 links. Renaming a whole piece for every link costs up to n each, so the links cost m × n: 20 billion steps. A union-find structure joins two pieces in nearly constant time, so the whole count takes about 300,000 steps.
count_pieces · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.