Advertisement
Guest User

Grupuri și grupulețe

a guest
Aug 24th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.50 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <queue>
  7.  
  8. struct Node {
  9.     std::vector<int> neighbors;
  10. };
  11.  
  12. class ListGraph {
  13. private:
  14.     std::vector<Node> nodes;
  15.     std::vector<bool> visited;
  16.     int size;
  17.  
  18. public:
  19.     ListGraph(int sz) {
  20.         /* Nodes are numbered 1 to N, not 0 to N. */
  21.         size = sz;
  22.         nodes.resize(sz + 1);
  23.         for (int i = 0; i < sz + 1; i++)
  24.             visited.push_back(false);
  25.     }
  26.  
  27.     ~ListGraph() {}
  28.  
  29.     void addEdge(int src, int dst) {
  30.         nodes[src].neighbors.push_back(dst);
  31.     }
  32.    
  33.     /* you might want to write your own compare function.. check the problem statement */
  34.     static bool compare_groups(std::vector<int> v1, std::vector<int> v2) {
  35.         /* TODO: compare 2 groups properly */
  36.         return v1[0] < v2[0];
  37.     }
  38.    
  39.     /* get all groups in the classroom */
  40.     void dfs(int nod, std::vector<bool> &viz, std::vector<int> &bis) {
  41.         bis.push_back(nod);
  42.         viz[nod] = 1;
  43.         for (int i = 0; i < nodes[nod].neighbors.size(); i++) {
  44.             if (viz[nodes[nod].neighbors[i]] == 0) {
  45.                 dfs(nodes[nod].neighbors[i], viz, bis);
  46.             }
  47.         }
  48.     }
  49.     std::vector<std::vector<int> > get_groups() {
  50.         std::vector<std::vector<int> > bisericute;
  51.         /* TODO: do your magic */
  52.         int nr = 0;
  53.         for (int i = 1; i <= size; i++) {
  54.             if (visited[i] == false) {
  55.                 bisericute.push_back({});
  56.                 dfs(i, visited, bisericute[nr]);
  57.                 std::sort(bisericute[nr].begin(), bisericute[nr].end());
  58.                 nr++;
  59.             }
  60.         }
  61.         /* TODO: return 'bisericute' sorted as described in the problem statement */
  62.         std::sort(bisericute.begin(), bisericute.end(), compare_groups);
  63.         return bisericute;
  64.     }
  65.  
  66. };
  67.  
  68. int main() {
  69.     /* DO NOT CHANGE ANYTHING HERE! */
  70.     int N, M, from, to;
  71.     std::vector<std::vector<int> > bisericute;
  72.    
  73.     std::cin >> N >> M;
  74.     ListGraph g(N);
  75.     for (int i = 0; i < M; i++) {
  76.         std::cin >> from >> to;
  77.         g.addEdge(from, to);
  78.         g.addEdge(to, from);
  79.     }
  80.    
  81.     bisericute = g.get_groups();
  82.     std::cout << bisericute.size() << std::endl;
  83.     for (int i = 0; i < bisericute.size(); i++) {
  84.         for (int j = 0; j < bisericute[i].size(); j++) {
  85.             std::cout << bisericute[i][j] << " ";
  86.         }
  87.         std::cout << std::endl;
  88.     }
  89.      
  90.     return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement