Advertisement
ShabbaWings

Untitled

Oct 20th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.48 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);
  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);
  18. }
  19. }
  20. return summ;
  21. }
  22. }
  23.  
  24. int second(vector<vector<int>>& a, int i, vector<int>& visited) {
  25. visited[i] = 1;
  26. if (a[i].size() == 0) {
  27. return 0;
  28. } else {
  29. int summ = 0;
  30. for (int j = 0; j < a[i].size(); ++j) {
  31. if (visited[a[i][j]] == 0) {
  32. summ += first(a, a[i][j], visited);
  33. }
  34. }
  35. return summ;
  36. }
  37. }
  38.  
  39. int main() {
  40. int v;
  41. cin >> v;
  42. vector<vector<int>> a(v);
  43. for (int i = 0; i < v; ++i) {
  44. vector<int> d;
  45. int k;
  46. cin >> k;
  47. for (int j = 0; j < k; ++j) {
  48. int b;
  49. cin >> b;
  50. d.push_back(b);
  51. }
  52. a[i] = d;
  53. }
  54. vector<int> visitedFirst(v, 0), visitedSecond(v, 0);
  55. int answer = 0;
  56. for (int i = 0; i < v; ++i) {
  57. if (visitedFirst[i] == 0) {
  58. answer += min(first(a, i, visitedFirst), second(a, i, visitedSecond));
  59. }
  60. }
  61. cout << answer;
  62. return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement