Simple DFS solution | C# | +95% efficient
Intuition\n Describe your first thoughts on how to solve this problem. \nApply DFS algorithm and keep track of the visited nodes. If all nodes are not covered i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nApply DFS algorithm and keep track of the visited nodes. If all nodes are not covered in a single trace of DFS, it implies multiple components are present.\nThe number of such independent/dis-connected components is equals to the number of times we call the DFS from the top level (not including the recursive call, but the one we make at top level)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAs mentioned in the intuition, to find the number of disconnected components in graph check the number of times we need to make a DFS call explicity on the non-visited nodes.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n) - as we need visit all nodes once\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) as we are using a hashset to keep track of visited nodes.\n\n# Code\n```\npublic class Solution {\n    public int FindCircleNum(int[][] isConnected) {\n        int count = 0;\n        HashSet<int> h = new HashSet<int>();\n        for (int i = 0; i < isConnected.Length; i++)\n        {\n            if (!h.Contains(i))\n            {\n                h.Add(i);\n                DFS(isConnected, i, h);\n                count++;\n            }\n        }\n        \n        return count;\n    }\n    \n    private void DFS(int[][] graph, int i, HashSet<int> h)\n    {\n        for (int j = 0; j < graph[i].Length; j++)\n        {\n            if (i != j && graph[i][j] == 1 && !h.Contains(j))\n            {\n                h.Add(j);\n                DFS(graph, j, h);\n            }\n        }\n    }\n}\n```
['Depth-First Search', 'Graph', 'C#']