//#include #include #include #include using std::vector; using std::pair; void explore(vector> &adj, vector &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[v][i]); } } int number_of_components(vector > &adj) { vector visited; 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(ConnectedComponents, cc1) { // vector> adj = { { 1 }, {0, 2 }, { 1 }, { } }; // ASSERT_EQ(number_of_components(adj), 2); //} int main() { size_t n, m; std::cin >> n >> m; vector > adj(n, vector()); for (size_t i = 0; i < m; i++) { int x, y; std::cin >> x >> y; adj[x - 1].push_back(y - 1); adj[y - 1].push_back(x - 1); } std::cout << number_of_components(adj); }