Advertisement
Guest User

Untitled

a guest
Oct 15th, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. #include <queue>
  5. #include <set>
  6.  
  7.  
  8. using namespace std;
  9.  
  10. struct vertex {
  11.     set<int> connected;
  12.     int edges;
  13. };
  14.  
  15. void fillTrees(vector<vertex> &trees, int v) {
  16.     for (int i = 0; i != v; ++i) {
  17.         int d;
  18.         cin >> d;
  19.         trees[i].edges = d;
  20.         for (int j = 0; j != d; ++j) {
  21.             int vert;
  22.             cin >> vert;
  23.             trees[i].connected.insert(vert);
  24.         }
  25.     }
  26. }
  27.  
  28.  
  29. void findAns(vector<vertex> &trees) {
  30.     queue<int> checkList;
  31.     int counter = 0;
  32.     for (int i = 0; i != trees.size(); ++i)
  33.         checkList.push(i);
  34.     while (!checkList.empty()) {
  35.         int i = checkList.front();
  36.         checkList.pop();
  37.         if(trees[i].edges == 1) {
  38.             int point = *trees[i].connected.begin();
  39.             for (auto it = trees[point].connected.begin(); it != trees[point].connected.end(); ++it) {
  40.                 if (trees[*it].edges != 0) {
  41.                     trees[*it].connected.erase(point);
  42.                     trees[*it].edges--;
  43.                 }
  44.             }
  45.             trees[point].edges = 0;
  46.             counter++;
  47.         } else if (trees[i].edges > 1){
  48.             checkList.push(i);
  49.         }
  50.     }
  51.     cout << counter;
  52. }
  53.  
  54. int main() {
  55.     int v;
  56.     cin >> v;
  57.     vector<vertex> trees(v);
  58.     fillTrees(trees, v);
  59.     findAns(trees);
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement