Advertisement
achulkov2

Untitled

Oct 16th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. vector<set<int>> graph;
  8. set<int> leaves;
  9. vector<int> deg, take;
  10.  
  11. int main() {
  12.     int n;
  13.     cin >> n;
  14.     deg.resize(n);
  15.     graph.resize(n);
  16.     for (int i = 0; i < n; ++i) {
  17.         int c;
  18.         cin >> c;
  19.         if (c == 1) {
  20.             leaves.insert(i);
  21.         }
  22.         deg[i] = c;
  23.         for (int j = 0; j < c; ++j) {
  24.             int x;
  25.             cin >> x;
  26.             graph[i].insert(x);
  27.         }
  28.     }
  29.     take.assign(n, 2);
  30.     while (!leaves.empty()) {
  31.         int u = *leaves.begin();
  32.         if (deg[u] == 1) {
  33.             take[u] = 0;
  34.             int v = *graph[u].begin();
  35.             take[v] = 1;
  36.             while (!graph[v].empty()) {
  37.                 int t = *graph[v].begin();
  38.                 graph[t].erase(v);
  39.                 --deg[t];
  40.                 if (deg[t] == 1) leaves.insert(t);
  41.                 graph[v].erase(graph[v].begin());
  42.             }
  43.             deg[v] = 0;
  44.         }
  45.         leaves.erase(u);
  46.     }
  47.     int ans = 0;
  48.     for (int i = 0; i < n; ++i) {
  49.         if (take[i] == 1) {
  50.             ++ans;
  51.         }
  52.     }
  53.     cout << ans << "\n";
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement