artemgf

Метро не в Екатеринбурге

Oct 28th, 2017
316
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <map>
  6. #include <queue>
  7. #include <set>
  8.  
  9. using namespace std;
  10. struct top
  11. {
  12.     int num;
  13.     bool was;
  14.     vector <top*> next;
  15. };
  16.  
  17. top* newtop(int num)
  18. {
  19.     top* prom = new top();
  20.     prom->num = num;
  21.     prom->was = false;
  22.     return prom;
  23. }
  24.  
  25. void findbreas(top* Top)
  26. {
  27.     queue <top*>nexta;
  28.  
  29.     nexta.push(Top);
  30.  
  31.     while (nexta.size() != 0)
  32.     {
  33.         top* prom = nexta.front();
  34.         nexta.pop();
  35.         for (auto i = prom->next.begin(); i != prom->next.end(); i++)
  36.         {
  37.             if ((*i)->was != true)
  38.             {
  39.                 nexta.push(*i);
  40.                 (*i)->was = true;
  41.             }
  42.         }
  43.     }
  44. }
  45. int main()
  46. {
  47.     int n, k, m;
  48.     int prom, promk;
  49.     cin >> n >> k >> m;
  50.  
  51.     map<int, vector<int>> stans;
  52.     map<int, top*>graf;
  53.  
  54.     for (int i = 1; i <= n; i++)
  55.     {
  56.         top* New = newtop(i);
  57.         graf[New->num] = New;
  58.     }
  59.  
  60.     for (int i = 1; i <= k; i++)
  61.     {
  62.         cin >> prom >> promk;
  63.         graf[prom]->next.push_back(graf[promk]);
  64.         graf[promk]->next.push_back(graf[prom]);
  65.     }
  66.  
  67.     int svaz = 0;
  68.     for (auto i = graf.begin(); i != graf.end(); i++)
  69.     {
  70.         if (i->second->was != true)
  71.         {
  72.             findbreas(i->second);
  73.             svaz++;
  74.         }
  75.     }
  76.     cout << svaz - 1<< endl;
  77.  
  78.     system("pause");
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment