Advertisement
Derga

Untitled

Oct 29th, 2023
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. struct Node {
  7. Node* next_;
  8. Node() : next_(nullptr) {};
  9. Node(Node* next) : next_(next) {};
  10. };
  11.  
  12. int main() {
  13. int nodes_count;
  14. cin >> nodes_count;
  15. vector<Node> list(1 + nodes_count);
  16. for (int i = 1; i <= nodes_count; ++i) {
  17. int next_node_idx;
  18. cin >> next_node_idx;
  19. list[i].next_ = &list[next_node_idx];
  20. }
  21.  
  22. //рассматриваю случай, что нет петель
  23. Node* turtle = &list[1];
  24. Node* rabbit = &list[2];
  25.  
  26. while (turtle && rabbit && turtle != rabbit && turtle->next_ && rabbit->next_ && rabbit->next_->next_) {
  27. turtle = turtle->next_;
  28. rabbit = rabbit->next_->next_;
  29. }
  30. if (!turtle || !rabbit) {
  31. cout << -1;
  32. return 0;
  33. }
  34.  
  35. int circle_size = 1;
  36. turtle = turtle->next_;
  37. while (turtle != rabbit) {
  38. circle_size++;
  39. turtle = turtle->next_;
  40. }
  41. cout << circle_size;
  42.  
  43. return 0;
  44. }
  45. /*
  46. test1
  47. 6
  48. 3 4 5 5 6 2
  49.  
  50. 4
  51.  
  52. это не пройдет сейчас
  53. test2
  54. 3
  55. 2 3
  56.  
  57. -1
  58. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement