Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Основы теории графов и dfs. Теория. Задача E.
- #include <bits/stdc++.h>
- using namespace std;
- int n, m;
- vector < vector < int > > g;
- vector < bool > used;
- vector < int > cur;
- void dfs(int v) {
- if (used[v]) return;
- used[v] = true;
- cur.push_back(v + 1);
- for (auto u : g[v]) {
- dfs(u);
- }
- }
- int main() {
- cin >> n >> m;
- g.resize(n);
- used.resize(n, false);
- for (int i = 0; i < m; i++) {
- int a, b;
- cin >> a >> b;
- a--; b--;
- g[a].push_back(b);
- g[b].push_back(a);
- }
- vector < vector < int > > ans;
- for(int i = 0; i < n; i++) {
- if (!used[i]) {
- cur.clear();
- dfs(i);
- ans.push_back(cur);
- }
- }
- cout << ans.size() << endl;
- for (auto &e : ans) {
- sort(e.begin(), e.end());
- cout << e.size() << endl;
- for (auto v : e) {
- cout << v << " ";
- }
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement