summaryrefslogtreecommitdiff
path: root/Sources
diff options
context:
space:
mode:
authorHaidong Ji2020-05-16 22:53:20 -0500
committerHaidong Ji2020-05-16 22:53:20 -0500
commitda9e1015ccdf2ca53295f6e5c76b88d820956194 (patch)
tree5f564dcbb8a190051c05b6114ba0f5f85e907297 /Sources
parent0d2813a19dd37665102319bfe746b8975a080cef (diff)
Connected Components done, aka "Adding Exits to a Maze"
Diffstat (limited to 'Sources')
-rw-r--r--Sources/GraphAlgo.cpp40
1 files changed, 20 insertions, 20 deletions
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);
}