Count the provinces
A map shows n cities, numbered 0 to n - 1. You get an n by n grid connected of 0s and 1s: connected[i][j] is 1 when cities i and j have a direct road between them, and 0 when they do not. Roads go both ways, so connected[i][j] equals connected[j][i], and every city counts as linked to itself, so connected[i][i] is 1.
Two cities are in the same province when you can drive from one to the other, on one road or a chain of roads. Every city belongs to exactly one province, and a city with no roads is a province by itself. Return the number of provinces.
connected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]Output2The roads 0 to 3 and 1 to 2 make two provinces: {0, 3} and {1, 2}.
connected = [[1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 1, 1], [0, 0, 1, 1]]Output1The roads are 0 to 1, 1 to 2 and 2 to 3. City 0 reaches city 3 through 1 and 2, so all four are one province.
connected = [[1, 0, 1, 0, 0], [0, 1, 0, 0, 0], [1, 0, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1]]Output3{0, 2}, {3, 4}, and city 1 on its own.
1 ≤ n ≤ 1,000
connected[i][j]is 0 or 1connected[i][i]is 1, andconnected[i][j]equalsconnected[j][i]
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.