Advertisement
ShabbaWings

Untitled

Oct 20th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int second(vector<vector<int>>& a, int i, vector<int>& visited, vector<int>& visitedSecond);
  8.  
  9. int first(vector<vector<int>>& a, int i, vector<int>& visited) {
  10. visited[i] = 1;
  11. if (a[i].size() == 0) {
  12. return 1;
  13. } else {
  14. int summ = 1;
  15. for (int j = 0; j < a[i].size(); ++j) {
  16. if (visited[a[i][j]] == 0) {
  17. summ += second(a, a[i][j], visited, visited);
  18. }
  19. }
  20. return summ;
  21. }
  22. }
  23.  
  24. int second(vector<vector<int>>& a, int i, vector<int>& visited,
  25. vector<int>& visitedSecond) {
  26. visited[i] = 1;
  27. visitedSecond[i] = 1;
  28. if (a[i].size() == 0) {
  29. return 0;
  30. } else {
  31. int summ = 0;
  32. for (int j = 0; j < a[i].size(); ++j) {
  33. if (visited[a[i][j]] == 0) {
  34. summ += first(a, a[i][j], visited);
  35. }
  36. }
  37. return min(first(a, i, visitedSecond), summ);
  38. }
  39. }
  40.  
  41. int main() {
  42. int v;
  43. cin >> v;
  44. vector<vector<int>> a(v);
  45. for (int i = 0; i < v; ++i) {
  46. vector<int> d;
  47. int k;
  48. cin >> k;
  49. for (int j = 0; j < k; ++j) {
  50. int b;
  51. cin >> b;
  52. d.push_back(b);
  53. }
  54. a[i] = d;
  55. }
  56. vector<int> visitedFirst(v, 0), visitedSecond(v, 0);
  57. int answer = 0;
  58. int flag = 0;
  59. for (int i = 0; i < v; ++i) {
  60. if (visitedFirst[i] == 0) {
  61. answer += second(a, i, visitedSecond, visitedSecond);
  62. }
  63. }
  64. cout << answer;
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement