Algorithms : complete 03-algorithms_on_graphs 01-decomposition

1 files changed, 28 insertions, 5 deletions

diff --git a/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp b/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp
index 8e6b531..d6b148b 100644
--- a/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp
+++ b/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp
@@ -1,13 +1,36 @@
 #include <iostream>
 #include <vector>
+#include <stack>
 
 using std::vector;
+using std::stack;
 using std::pair;
 
-int number_of_components(vector<vector<int> > &adj) {
-  int res = 0;
-  //write your code here
-  return res;
+int number_of_components(vector<vector<int> > &adj)
+{
+    vector<bool> visited(adj.size());
+    stack<int> st;
+
+    int cc = 0;
+    for (int j = 0; j < adj.size(); j++) {
+        if (visited[j])
+            continue;
+        cc += 1;
+        st.push(j);
+        while(!st.empty()) {
+            int v = st.top();
+            st.pop();
+            visited[v] = true;
+            int s = adj[v].size();
+            for (int i = 0; i < s; i++) {
+                int w = adj[v][i];
+                if (!visited[w])
+                    st.push(w);
+            }
+        }
+    }
+
+    return cc;
 }
 
 int main() {
@@ -20,5 +43,5 @@ int main() {
     adj[x - 1].push_back(y - 1);
     adj[y - 1].push_back(x - 1);
   }
-  std::cout << number_of_components(adj);
+  std::cout << number_of_components(adj) << '\n';
 }