Create 547. Number of Provinces LeetCode

Medo3-coder · web-flow · commit 80d161a27610 · 2022-10-01T11:17:48.000+02:00
diff --git a/Graph/547. Number of Provinces LeetCode b/Graph/547. Number of Provinces LeetCode
@@ -0,0 +1,45 @@
+class Solution {
+    
+    private : 
+    void dfs(int node , vector<int> adjLs[] , vector<int> &visited)
+    {
+        visited[node] = 1 ;
+        for(auto it : adjLs[node])
+        {
+            if(!visited[it])
+            {
+                dfs(it , adjLs ,visited );
+            }
+        }
+    }
+public:
+    int findCircleNum(vector<vector<int>>& isConnected) {
+        int v = isConnected.size() ;
+        vector<int> visited(v , 0);
+        vector<int> adjLs[v];
+        
+         // converting adjency matrix to list
+        for(int i = 0 ; i < v ; i++)
+        {
+            for(int j = 0 ; j < v ; j++)
+            {
+                if(isConnected[i][j] == 1 && i != j)
+                {
+                    adjLs[i].push_back(j);
+                    adjLs[j].push_back(i);
+                }
+            }
+        }
+        
+        int count = 0 ;
+        for(int i = 0 ; i < v ; i++)
+        {
+            if(!visited[i])
+            {
+                count++;
+                dfs(i , adjLs ,  visited);
+            }
+        }
+        return count ;
+    }
+};
