[LeetCode] Number of Provinces

Problem: There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Approach: Its kind of finding connected components in a graph problem. We will simply count the number of times we need to do a DFS until all the nodes are visited.

Implementation in C#:

    public int FindCircleNum(int[][] isConnected)

    {

        int rows = isConnected?.Length ?? 0;

        if (rows == 0)

        {

            return 0;

        }

        int cols = isConnected[0].Length;

        HashSet<int> visited = new HashSet<int>();

        int numOfProvinces = 0;

        for (int node = 0; node < rows; ++node)

        {

            if (!visited.Contains(node))

            {

                this.FindCircleNumDFS(node, isConnected, visited);

                ++numOfProvinces;

            }

        }

        return numOfProvinces;

    }

    private void FindCircleNumDFS(int node,

                                  int[][] isConnected,

                                  HashSet<int> visited)

    {

        if (visited.Contains(node))

        {

            return;

        }

        visited.Add(node);

        for (int i = 0; i < isConnected[0].Length; ++i)

        {

            if (isConnected[node][i] == 1)

            {

                this.FindCircleNumDFS(i, isConnected, visited);

            }

        }

    }

Complexity: O(n^2)