Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <iterator>
- #include <unordered_map>
- #include <unordered_set>
- #include <string>
- class Graph {
- private:
- int size_g;
- std::vector<std::vector<bool>> data;
- std::vector<int> used;
- public:
- std::vector<bool> isused;
- Graph() {
- }
- explicit Graph(int n) {
- data.resize(n);
- size_g = n;
- for (int i = 0; i < n; i++) {
- data[i].resize(n);
- }
- isused.resize(n);
- }
- void insert(int a, int b) {
- data[a - 1][b - 1] = true;
- data[b - 1][a - 1] = true;
- }
- void subgraph2(int a) {
- if (!isused[a - 1]) {
- isused[a - 1] = true;
- used.push_back(a);
- for (int i = 0; i < size_g; i++) {
- if (data[a - 1][i]) {
- subgraph2(i + 1);
- }
- }
- }
- }
- std::vector<int> subgraph(int a) {
- used = {};
- subgraph2(a);
- return used;
- }
- };
- int main() {
- int N, M;
- int a, b;
- std::cin >> N >> M;
- if (N != 0 && M != 0) {
- Graph graph(N);
- for (int i = 0; i < M; i++) {
- std::cin >> a >> b;
- graph.insert(a, b);
- }
- std::vector<std::vector<int>> result;
- for (int i = 0; i < N; i++) {
- if (!graph.isused[i]) {
- result.push_back(graph.subgraph(i + 1));
- }
- }
- std::cout << result.size() << '\n';
- for (int i = 0; i < result.size(); i++) {
- std::cout << result[i].size() << '\n';
- std::cout << result[i][0];
- for (int j = 1; j < result[i].size(); j++) {
- std::cout << " " << result[i][j];
- }
- std::cout << '\n';
- }
- } else if (N == 0) {
- std::cout << 0;
- } else {
- std::cout << N << '\n';
- for (int i = 0; i < N; i++) {
- std::cout << 1 << '\n' << i + 1 << '\n';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement