From da9e1015ccdf2ca53295f6e5c76b88d820956194 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sat, 16 May 2020 22:53:20 -0500
Subject: Connected Components done, aka "Adding Exits to a Maze"

---
 Sources/GraphAlgo.cpp | 40 ++++++++++++++++++++--------------------
 1 file changed, 20 insertions(+), 20 deletions(-)

(limited to 'Sources')

diff --git a/Sources/GraphAlgo.cpp b/Sources/GraphAlgo.cpp
index 8836b2f..a950767 100644
--- a/Sources/GraphAlgo.cpp
+++ b/Sources/GraphAlgo.cpp
@@ -7,30 +7,32 @@
 using std::vector;
 using std::pair;
 
-void explore(vector<vector<int>> &adj, vector<int> &visited, int x, int y) {
-	visited.push_back(x);
-	if (x == y)
-		return;
-	for (size_t i = 0; i < adj[x].size(); i++) {
-		if (std::find(visited.begin(), visited.end(), adj[x][i])
+void explore(vector<vector<int>> &adj, vector<int> &visited, int v) {
+	visited.push_back(v);
+
+	for (size_t i = 0; i < adj[v].size(); i++) {
+		if (std::find(visited.begin(), visited.end(), adj[v][i])
 				== visited.end())
-			explore(adj, visited, adj[x][i], y);
+			explore(adj, visited, adj[v][i]);
 	}
 }
 
-int reach(vector<vector<int> > &adj, int x, int y) {
+int number_of_components(vector<vector<int> > &adj) {
+
 	vector<int> visited;
-	if (x == y)
-		return 1;
-	explore(adj, visited, x, y);
-	if (std::find(visited.begin(), visited.end(), y) != visited.end())
-		return 1;
-	return 0;
+	int cc = 0;
+	for (size_t v = 0; v < adj.size(); v++) {
+		if (std::find(visited.begin(), visited.end(), v) == visited.end()) {
+			explore(adj, visited, v);
+			cc++;
+		}
+	}
+	return cc;
 }
 
-//TEST(Reachable, Reach1) {
-//	vector<vector<int>> adj = { { 1, 3 }, { }, { 1 }, { 2 } };
-//	ASSERT_EQ(reach(adj, 0, 3), 1);
+//TEST(ConnectedComponents, cc1) {
+//	vector<vector<int>> adj = { { 1 }, {0, 2 }, { 1 }, { } };
+//	ASSERT_EQ(number_of_components(adj), 2);
 //}
 
 int main() {
@@ -43,7 +45,5 @@ int main() {
     adj[x - 1].push_back(y - 1);
     adj[y - 1].push_back(x - 1);
   }
-  int x, y;
-  std::cin >> x >> y;
-  std::cout << reach(adj, x - 1, y - 1);
+  std::cout << number_of_components(adj);
 }
-- 
cgit v1.2.3