diff --git a/SConstruct b/SConstruct
index e92a895..5bfbec7 100644
--- a/SConstruct
+++ b/SConstruct
@@ -103,6 +103,7 @@
                    postinstall_runner_action.cc
                    set_bootable_flag_action.cc
                    subprocess.cc
+                   tarjan.cc
                    update_check_action.cc
 		               update_metadata.pb.cc
 		               utils.cc""")
@@ -130,6 +131,7 @@
                             postinstall_runner_action_unittest.cc
                             set_bootable_flag_action_unittest.cc
                             subprocess_unittest.cc
+                            tarjan_unittest.cc
                             test_utils.cc
                             update_check_action_unittest.cc
                             utils_unittest.cc""")
diff --git a/tarjan.cc b/tarjan.cc
new file mode 100644
index 0000000..aaca7d0
--- /dev/null
+++ b/tarjan.cc
@@ -0,0 +1,70 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <algorithm>
+#include <vector>
+#include "chromeos/obsolete_logging.h"
+#include "update_engine/tarjan.h"
+#include "update_engine/utils.h"
+
+using std::min;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+const vector<Vertex>::size_type kInvalidIndex = -1;
+}
+
+void TarjanAlgorithm::Execute(Vertex::Index vertex,
+                              Graph* graph,
+                              vector<Vertex::Index>* out) {
+  stack_.clear();
+  components_.clear();
+  index_ = 0;
+  for (Graph::iterator it = graph->begin(); it != graph->end(); ++it)
+    it->index = it->lowlink = kInvalidIndex;
+  required_vertex_ = vertex;
+
+  Tarjan(vertex, graph);
+  if (!components_.empty())
+    out->swap(components_[0]);
+}
+
+void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) {
+  CHECK_EQ((*graph)[vertex].index, kInvalidIndex);
+  (*graph)[vertex].index = index_;
+  (*graph)[vertex].lowlink = index_;
+  index_++;
+  stack_.push_back(vertex);
+  for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin();
+       it != (*graph)[vertex].out_edges.end(); ++it) {
+    Vertex::Index vertex_next = it->first;
+    if ((*graph)[vertex_next].index == kInvalidIndex) {
+      Tarjan(vertex_next, graph);
+      (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
+                                     (*graph)[vertex_next].lowlink);
+    } else if (utils::VectorContainsValue(stack_, vertex_next)) {
+      (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
+                                     (*graph)[vertex_next].index);
+    }
+  }
+  if ((*graph)[vertex].lowlink == (*graph)[vertex].index) {
+    vector<Vertex::Index> component;
+    Vertex::Index other_vertex;
+    do {
+      other_vertex = stack_.back();
+      stack_.pop_back();
+      component.push_back(other_vertex);
+    } while (other_vertex != vertex && !stack_.empty());
+      
+    if (utils::VectorContainsValue(component, required_vertex_)) {
+      components_.resize(components_.size() + 1);
+      component.swap(components_.back());
+    }
+  }
+}
+
+}  // namespace chromeos_update_engine
+
diff --git a/tarjan.h b/tarjan.h
new file mode 100644
index 0000000..1a80a95
--- /dev/null
+++ b/tarjan.h
@@ -0,0 +1,39 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H__
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H__
+
+// This is an implemenation of Tarjan's algorithm which finds all
+// Strongly Connected Components in a graph.
+
+// Note: a true Tarjan algorithm would find all strongly connected components
+// in the graph. This implementation will only find the strongly connected
+// component containing the vertex passed in.
+
+#include <vector>
+#include "update_engine/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class TarjanAlgorithm {
+ public:
+  TarjanAlgorithm() : index_(0), required_vertex_(0) {}
+
+  // 'out' is set to the result if there is one, otherwise it's untouched.
+  void Execute(Vertex::Index vertex,
+               Graph* graph,
+               std::vector<Vertex::Index>* out);
+ private:
+  void Tarjan(Vertex::Index vertex, Graph* graph);
+
+  Vertex::Index index_;
+  Vertex::Index required_vertex_;
+  std::vector<Vertex::Index> stack_;
+  std::vector<std::vector<Vertex::Index> > components_;
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H__
diff --git a/tarjan_unittest.cc b/tarjan_unittest.cc
new file mode 100644
index 0000000..9c4d7a8
--- /dev/null
+++ b/tarjan_unittest.cc
@@ -0,0 +1,80 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <utility>
+#include <gtest/gtest.h>
+#include "chromeos/obsolete_logging.h"
+#include "update_engine/graph_types.h"
+#include "update_engine/tarjan.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class TarjanAlgorithmTest : public ::testing::Test {};
+
+TEST(TarjanAlgorithmTest, SimpleTest) {
+  const Vertex::Index n_a = 0;
+  const Vertex::Index n_b = 1;
+  const Vertex::Index n_c = 2;
+  const Vertex::Index n_d = 3;
+  const Vertex::Index n_e = 4;
+  const Vertex::Index n_f = 5;
+  const Vertex::Index n_g = 6;
+  const Vertex::Index n_h = 7;
+  const Graph::size_type kNodeCount = 8;
+
+  Graph graph(kNodeCount);
+  
+  graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
+  graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
+  graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
+  graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
+  graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties()));
+  graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties()));
+  graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties()));
+  
+  TarjanAlgorithm tarjan;
+  
+  for (Vertex::Index i = n_a; i <= n_e; i++) {
+    vector<Vertex::Index> vertex_indexes;
+    tarjan.Execute(i, &graph, &vertex_indexes);
+
+    EXPECT_EQ(5, vertex_indexes.size());
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_a));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_b));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_c));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_d));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_e));
+  }
+  
+  {
+    vector<Vertex::Index> vertex_indexes;
+    tarjan.Execute(n_f, &graph, &vertex_indexes);
+    
+    EXPECT_EQ(1, vertex_indexes.size());
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_f));
+  }
+  
+  for (Vertex::Index i = n_g; i <= n_h; i++) {
+    vector<Vertex::Index> vertex_indexes;
+    tarjan.Execute(i, &graph, &vertex_indexes);
+
+    EXPECT_EQ(2, vertex_indexes.size());
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_g));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_h));
+  }
+}
+
+}  // namespace chromeos_update_engine
diff --git a/utils.h b/utils.h
index 9354ba5..22a1ce8 100644
--- a/utils.h
+++ b/utils.h
@@ -5,6 +5,7 @@
 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_UTILS_H__
 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_UTILS_H__
 
+#include <algorithm>
 #include <set>
 #include <string>
 #include <vector>