Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- bool mark[100000] = {};
- int dfs(int s, vector<vector<long long> >& v , vector<long long>& res) {
- int cnt = 1;
- mark[s] = 1;
- for (int i = 0 ; i < v[s].size(); ++i) {
- if (mark[v[s][i]] != 1) {
- cnt += dfs(v[s][i], v, res);
- res.push_back(v[s][i]);
- }
- }
- return cnt;
- }
- int main () {
- int n, m;
- cin >> n >> m;
- vector <vector < long long > > v(n);
- vector <vector < long long > > res;
- for (int i = 0 ; i < m ; ++i) {
- int a, b;
- cin >> a >> b;
- v[a - 1].push_back(b - 1);
- v[b - 1].push_back(a - 1);
- }
- for (int i = 0; i < n; ++i) {
- if (mark[i]) continue;
- vector<long long > tmp;
- tmp.push_back(i);
- dfs(i, v, tmp);
- res.push_back(tmp);
- }
- cout << res.size() << "\n" ;
- for (int i = 0; i < res.size(); ++i) {
- cout << res[i].size() << "\n";
- for (int j = 0; j < res[i].size(); ++j) {
- cout << res[i][j] + 1 << " ";
- }
- cout << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement