diff options
| -rw-r--r-- | Sources/GraphAlgo.cpp | 40 |
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); } |