Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- using namespace std;
- void dfs(int v, vector <vector <int> > &g, vector <char> &used, vector <set<int>> &xx, set <int> &vv) {
- used[v] = true;
- vv.insert(v);
- for (int i = 0; i < g[v].size(); i++){
- if (used[g[v][i]] == 0){
- dfs(g[v][i], g, used, xx, vv);
- }
- }
- }
- int main() {
- int n, m;
- cin >> n >> m;
- vector <vector <int>> g(n);
- for (int i = 0; i < m; i++) {
- int q, q1;
- cin >> q >> q1;
- q--;
- q1--;
- g[q].push_back(q1);
- g[q1].push_back(q);
- }
- int cmp_cnt=0;
- vector <char> used(n, false);
- vector <set<int>> xx(cmp_cnt); // компонента - вершины
- for (int i = 0; i<n; i++) {
- if (!used[i]) {
- set <int> vv; // вершины компоненты
- dfs(i,g,used, xx, vv);
- xx[cmp_cnt]=vv;
- cmp_cnt++;
- }
- } cout << cmp_cnt;
- for (int i = 0; i<cmp_cnt; i++) {
- cout << i << endl;
- for (auto c : xx[i]) cout << c << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement