Advertisement
Guest User

Untitled

a guest
Oct 20th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <queue>
  4.  
  5. int main() {
  6. int vertex, degree, num, helper;
  7. std::cin >> vertex;
  8. std::vector<std::pair<int, int>> able(vertex);
  9. std::vector<int> used(vertex);
  10. std::vector<std::vector<int>> graph(vertex);
  11. std::queue<int> que;
  12. for (int i = 0; i != vertex; ++i) {
  13. std::cin >> degree;
  14. used[i] = degree - 1;
  15. able[i].second = 1;
  16. if (degree == 1) {
  17. que.push(i);
  18. used[i] = -1;
  19. }
  20. for (int j = 0; j != degree; ++j) {
  21. std::cin >> num;
  22. graph[i].push_back(num);
  23. }
  24. }
  25. for (int i = 0; i != vertex; ++i) {
  26. if (graph[i].size() == 1) {
  27. able[i].first = 0;
  28. }
  29. }
  30.  
  31. while (!que.empty()) {
  32. int vert_1 = que.front();
  33. helper = vert_1;
  34. que.pop();
  35. for (int i = 0; i != graph[vert_1].size(); ++i) {
  36. int vert_2 = graph[vert_1][i];
  37. if (used[vert_2] > 0) {
  38. used[vert_2] -= 1;
  39. able[vert_2].second += able[vert_1].second;
  40. able[vert_2].first = std::min(able[vert_2].second, able[vert_1].second);
  41. } else if (used[vert_2] == 0) {
  42. que.push(vert_2);
  43. used[vert_2] = -1;
  44. }
  45. }
  46. }
  47. std::cout << std::min(able[helper].first, able[helper].second) << '\n';
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement