#24. Dinamik graf — komponentlar soni
Dastlab sizda n ta cho'qqidan (tugundan) iborat, ammo hech qanday qirralarga ega bo'lmagan graf bor. Sizga ketma-ket q ta operatsiya beriladi. Har bir operatsiya add u v ko'rinishida bo'lib, u grafdagi u va v cho'qqilari orasiga yangi qirra qo'shishni anglatadi. Sizning vazifangiz har bir qirra qo'shilganidan so'ng, grafda nechta mustaqil bog'lanishli komponent (connected component) qolganligini aniqlashdir.
Birinchi qatorda n va q sonlari. Keyingi q ta qatorda add u v formatidagi operatsiyalar beriladi (1 <= u, v <= n).
Har bir operatsiyadan so'ng joriy komponentlar sonini alohida qatorda chiqaring.
1 ≤ n, q ≤ 2×10⁵
Initially, you have a graph consisting of n vertices (nodes) but no edges. You are given a sequence of q operations. Each operation is in the format add u v, which means adding a new edge between vertices u and v in the graph. Your task is to determine the number of independent connected components remaining in the graph after each edge is added.
The first line contains the numbers n and q. The next q lines contain operations in the add u v format (1 <= u, v <= n).
After each operation, output the current number of components on a new line.
1 ≤ n, q ≤ 2×10⁵
Изначально у вас есть граф, состоящий из n вершин (узлов), но не имеющий ребер. Вам дается последовательность из q операций. Каждая операция имеет формат add u v, что означает добавление нового ребра между вершинами u и v в графе. Ваша задача — определить количество независимых компонент связности, оставшихся в графе после добавления каждого ребра.
В первой строке заданы числа n и q. В следующих q строках заданы операции в формате add u v (1 <= u, v <= n).
После каждой операции выводите текущее количество компонент в отдельной строке.
1 ≤ n, q ≤ 2×10⁵
Dastlab sizda n ta cho'qqidan (tugundan) iborat, ammo hech qanday qirralarga ega bo'lmagan graf bor. Sizga ketma-ket q ta operatsiya beriladi. Har bir operatsiya add u v ko'rinishida bo'lib, u grafdagi u va v cho'qqilari orasiga yangi qirra qo'shishni anglatadi. Sizning vazifangiz har bir qirra qo'shilganidan so'ng, grafda nechta mustaqil bog'lanishli komponent (connected component) qolganligini aniqlashdir.
Kiruvchi ma'lumotlar
Birinchi qatorda n va q sonlari. Keyingi q ta qatorda add u v formatidagi operatsiyalar beriladi (1 <= u, v <= n).
Chiquvchi ma'lumotlar
Har bir operatsiyadan so'ng joriy komponentlar sonini alohida qatorda chiqaring.
Cheklovlar
1 ≤ n, q ≤ 2×10⁵
Misollar
3 2 add 1 2 add 2 3
2 1