Number of provinces

Count the connected components of an undirected graph: groups of cities linked directly or indirectly.

The idea

Scan every node. Whenever you find one that has not been visited, it belongs to a province nobody has counted yet: count it, then DFS (or BFS) outward to mark every node reachable from it, so the same province is never counted twice.

Code

public static int CountProvinces(Dictionary<char, List<char>> graph) {
    var seen = new HashSet<char>();
    int count = 0;
    foreach (char u in graph.Keys)
        if (seen.Add(u)) { count++; Visit(u, graph, seen); }
    return count;
}

static void Visit(char u, Dictionary<char, List<char>> graph, HashSet<char> seen) {
    foreach (char v in graph[u])
        if (seen.Add(v)) Visit(v, graph, seen);
}

Tips

• LeetCode phrases this with an isConnected adjacency matrix, but the moment you build the adjacency list from it, it is the exact same component count.
• Union-find solves this too: the final number of distinct roots is the number of provinces.

In the .NET library

This pattern, "scan for an unvisited node, flood fill, count", is the same shape as counting islands in a grid; a grid is just a graph where each cell links to its four neighbours.