fork(1) download
copy 
  1. #include <iostream>
  2. #include <utility>
  3. #include <list>
  4. #include <set>
  5. #include <iterator>
  6. #include <algorithm>
  7. #include <map>
  8.  
  9.  
  10. //количество вершин
  11. uint N;
  12. //количество ребер
  13. uint K;
  14. //список ребер
  15. std::set<std::set<uint>> friend_groups;
  16.  
  17. std::set<std::set<uint>> friend_groups_next;
  18. //decltype(friend_groups) friend_groups_next;
  19.  
  20. //карта вершин, ключ - номер вершины, значение - множество соседних вершин
  21. std::map<uint, std::set<uint>> verts;
  22.  
  23.  
  24. //
  25. void input(){
  26.     //прочитать количество вершин
  27.     std::cin >> N;
  28.     //прочитать количество ребер
  29.     std::cin >> K;
  30.  
  31.     //для каждой вершины
  32.     for (uint i=1; i<=N; ++i){
  33.         //создать пустое множество соседей, потом заполним
  34.         verts.insert({i, {}});
  35.     }
  36.  
  37.     //для каждого ребра
  38.     for (uint i=0; i<K; ++i){
  39.         uint v1, v2;
  40.         //прочитать пару вершин
  41.         std::cin >> v1 >> v2;
  42.  
  43.         //добавить вершину v2 в множество соседей вершины v1
  44.         verts[v1].insert(v2);
  45.         //добавить вершину v1 в множество соседей вершины v2
  46.         verts[v2].insert(v1);
  47.  
  48.         //добавить ребро в список
  49.         friend_groups.insert({v1, v2});
  50.     }
  51. }
  52.  
  53. //укрупнить группки друзей
  54. void enlarge_friend_groups(){
  55.     for (const auto &friend_group: friend_groups) {
  56.         //соседние вершины подграфа
  57.         std::set<uint> neighbors;
  58.  
  59.         //объединить множества соседей вершин для каждой вершины в дружеской группе
  60.         for (auto it= friend_group.begin(); it != friend_group.end(); ++it){
  61.             const int &v = *it;
  62.             const std::set<uint> &n = verts[v];
  63.             neighbors.insert(n.begin(), n.end());
  64.         }
  65.  
  66.         //вычесть саму дружескую группу - образовать множество вершин-соседей с кучкой друзей
  67.         for (uint v: friend_group) {
  68.             neighbors.erase(v);
  69.         }
  70.  
  71.         //пройтись по соседям
  72.         for (uint neighbor: neighbors) {
  73.             if (std::all_of(friend_group.begin(), friend_group.end(), [neighbor, &friend_group](uint v){ return verts[neighbor].find(v) != verts[neighbor].end(); /*verts[v].find(neighbor) != friend_group.end();*/  }))
  74.             {
  75.                 std::set<uint> friend_group_next{neighbor};
  76.                 friend_group_next.insert(friend_group.begin(), friend_group.end());
  77.                 friend_groups_next.insert(std::move(friend_group_next));
  78.             }
  79.         }
  80.     }
  81. }
  82.  
  83.  
  84. int main()
  85. {
  86.     input();
  87.  
  88.     //пытаться увеличивать группы друзей на вершину до тех пор, пока это удается
  89.     //начинаем со списка ребер, как с наименьшего набора групп друзей - пар
  90.     do {
  91.         friend_groups_next.clear();
  92.         enlarge_friend_groups();
  93.         std::swap(friend_groups, friend_groups_next);
  94.  
  95.     } while (!friend_groups.empty());
  96.  
  97.     const std::set<uint> &result_group = *(friend_groups_next.begin());
  98.  
  99.  
  100.     std::cout << result_group.size() << std::endl;
  101.     std::copy(result_group.begin(), std::prev(result_group.end()), std::ostream_iterator<uint>(std::cout, " "));
  102.     std::cout << *(std::prev(result_group.end())) << std::endl;
  103.  
  104.     return 0;
  105. }
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
5
6
1 2
2 3
1 3
4 5
1 5
3 4
stdout
copy 
3
1 2 3
https://ideone.com/odyLzb
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!