Задача
Дан неориентированный невзвешенный граф. Требуется посчитать количество его компонент связности и вывести вершины каждой из них.
Входные данные
Во входном потоке заданы числа $N$ и $M$ ($0 < N \leqslant 100\,000$, $0 \leqslant M \leqslant 100\,000$) — число вершин и рёбер. В следующих $M$ строках указаны пары $i$, $j$ ($1 \leqslant i, j \leqslant N$), обозначающие неориентированное ребро между вершинами $i$ и $j$.
Выходные данные
В первой строке выведите количество компонент связности. Для каждой компоненты последовательно выведите две строки: количество вершин в компоненте и сами вершины в отсортированном порядке.
Пример
стандартный ввод стандартный вывод
6 4 3
3 1 3
1 2 1 2 3
5 4 2
2 3 4 5
1
6
Ограничения
- Время: 1 секунда
- Память: 256 мегабайт
Редакционный разбор
Построим списки смежности и запустим DFS/BFS. Как только находим непосещённую вершину $v$, стартуем обход, кладём все достигнутые вершины в вектор текущей компоненты, а после завершения сортируем его. Затем сохраняем компоненту к ответу и переходим к следующей непосещённой вершине.
Благодаря тому, что граф неориентированный, каждый переход по ребру обрабатывается один раз. Суммарная сложность обхода $O(N + M)$, а сортировки компонент дают дополнительный множитель $O(N \log N)$ в худшем случае, что укладывается в ограничения.
Формат вывода соответствует условию: сначала количество компонент, затем для каждой — размер и отсортированные вершины. Ниже пример реализации:
```cpp
vector<vector> g(n + 1);
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector used(n + 1);
vector<vector> comps;
for (int v = 1; v <= n; ++v) if (!used[v]) {
vector cur;
stack st;
used[v] = 1;
while (!st.empty()) {
int x = st.top(); st.pop();
cur.push_back(x);
for (int to : g[x]) if (!used[to]) {
used[to] = 1;
st.push(to);
}
}
sort(cur.begin(), cur.end());
comps.push_back(cur);
}
```
</details>
### Mentioned by
- [DFS1 — параллель B'](/dsa-notes/bp2025/contests/dfs1/){: .dsa-mention } — B: 2. Компоненты связности
- [Каталог задач](/dsa-notes/problems/){: .dsa-mention } — B: 2. Компоненты связности
