✅ C++ || easy solution || Step By Step Explanation
Approach\n### Understanding the Problem:\n\n- We need to determine the number of provinces (connected components) in a graph where cities are represented as nod
# Approach\n### Understanding the Problem:\n\n- We need to determine the number of provinces (connected components) in a graph where cities are represented as nodes and direct connections between cities are represented as edges.\n\n- The graph is represented as an `n x n` matrix isConnected, where `isConnected[i][j]` = 1 indicates that city `i` is directly connected to city `j`.\n\n### Graph Traversal:\n\n- To find all connected components (provinces), we can use Depth-First Search (DFS) or Breadth-First Search (BFS). Here, we\'ll use DFS.\n\n- Each time we initiate a DFS from an unvisited city, we identify a new province.\n\n### Algorithm Steps:\n\n- **Initialization**: Start by initializing a counter (answer) to keep track of the number of provinces. Create a `vector<bool>` called alreadyChecked to track which cities have been visited.\n\n- **Iterate Through Cities**: Loop through each city:\nIf the city has not been visited (`alreadyChecked[i] == false`), initiate a DFS from that city, which means we have found a new province. Increment the answer counter.\n\n- **DFS Implementation**: In the DFS function:\n    - If the current city (`cI`) has already been checked, return false (this indicates that we\u2019ve reached a city we\u2019ve already processed).\n    - Mark the current city as visited by setting `alreadyChecked[cI]` = true.\n    - Loop through all cities to find direct connections:\n    If there is a direct connection (`isConnected[cI][i] == 1`), recursively call DFS for city `i`.\n\n- **Return Result**: After iterating through all cities and performing DFS for each unvisited city, return the value of answer as the total number of provinces.\n\n\n# Complexity\n- Time complexity:\nThe time complexity of the algorithm is $$O(n^2)$$ where n is the number of cities. This is because we may need to traverse the entire adjacency matrix to check for direct connections for each city.\n\n- Space complexity:\nThe space complexity is $$O(n)$$ due to the additional space used by the alreadyChecked vector to keep track of visited cities. The recursion stack in the DFS function can also contribute to the space complexity in the worst case, leading to a total space complexity of $$O(n)$$.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int findCircleNum(vector<vector<int>>& isConnected) {\n        int answer = 0;\n        vector<bool> alreadyChecked(isConnected.size(), false);\n        for (int i = 0;i < isConnected.size();i++) {\n            if (dfs(isConnected, i, alreadyChecked)) {\n                answer++;\n            }\n        }\n        return answer;\n    }\n    bool dfs(vector<vector<int>>& isConnected,int cI, vector<bool>& alreadyChecked) {\n        if (alreadyChecked[cI]) {\n            return false;\n        }\n        alreadyChecked[cI] = true;\n        for (int i = 0;i < isConnected.size();i++) {\n            if(isConnected[cI][i] == 1) {\n                dfs(isConnected, i, alreadyChecked);\n            }\n        }\n        return true;\n    }\n};\n```\n\n![image.png](https://assets.leetcode.com/users/images/85564876-50c0-4208-8b08-97b1b9b5f99a_1727894513.7215683.png)\n
['C++']