//http://judge.openfmi.net:9280/practice/get_problem_description?contest_id=39&problem_id=112 #include #include int main() { int n, m; scanf("%d%d", &n, &m); int i; int *first = new int [n]; // the index of the first edge for each node int *to = new int [m * 2]; // the node which an edge connects int *next = new int [m * 2]; // the index of the next edge from the same node for (i = 0; i < n; ++i) { first[i] = -1; } int counter = 0; int x, y; for (i = 0; i < m; ++i) { scanf("%d%d", &x, &y); --x; --y; to[counter] = y; next[counter] = first[x]; first[x] = counter; ++counter; to[counter] = x; next[counter] = first[y]; first[y] = counter; ++counter; } bool *visited = new bool [n](); int *curr_front = new int [n]; int *prev_front = new int [n]; int curr_size; int prev_size; int node; int edge; int to_node; int result = 0; for (i = 0; i < n; ++i) { if (!visited[i]) { //start traversing the connected component ++result; // add the first node as a front curr_front[0] = i; curr_size = 1; visited[i] = true; // loop while we have nodes in the front while (curr_size) { std::swap(curr_size, prev_size); std::swap(curr_front, prev_front); curr_size = 0; // for each node in the front: // add all its neightbours in the next front for (int j = 0; j < prev_size; ++j) { node = prev_front[j]; edge = first[node]; while (edge != -1) { to_node = to[edge]; if (!visited[to_node]) { visited[to_node] = true; curr_front[curr_size++] = to_node; } edge = next[edge]; } } // If no more nodes are reachable, the next front will be 0 (curr_size) // and the loop ends. } } } printf("%d\n", result); }