Computer >> Máy Tính >  >> Lập trình >> C ++

Lồng mảng trong C ++

Giả sử chúng ta có một mảng A không được lập chỉ mục có độ dài N chứa tất cả các số nguyên từ 0 đến N-1. Chúng ta phải tìm và trả về độ dài dài nhất của tập S, trong đó S [i] ={A [i], A [A [i]], A [A [A [i]]], ...} phải chịu quy tắc dưới đây. Bây giờ hãy xem xét phần tử đầu tiên trong S bắt đầu với việc lựa chọn phần tử A [i] của index =i, phần tử tiếp theo trong S phải là A [A [i]], và sau đó là A [A [A [i]]]… Bằng cách tương tự đó, chúng ta ngừng thêm ngay trước khi một phần tử trùng lặp xuất hiện trong S. Vì vậy, nếu mảng giống như A =[5,4,0,3,1,6,2], thì đầu ra sẽ là 4, là A [ 0] =5, A [1] =4, A [2] =0, A [3] =3, A [4] =1, A [5] =6 và cuối cùng là A [6] =2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Vì vậy, hãy tạo một hàm có tên là dfs. Điều này sẽ đưa nút, mảng arr, mảng v và một tập hợp được truy cập. Làm như sau trong mảng dfs -
  • nếu nút được truy cập, sau đó quay lại
  • chèn nút vào v, đánh dấu nút là đã truy cập
  • dfs (arr [node], arr, v, đã truy cập)
  • Từ phương pháp chính, hãy thực hiện như sau -
  • ret:=0, n:=kích thước của nums. tạo một tập hợp được gọi là đã thăm
  • cho tôi trong phạm vi từ 0 đến n - 1
    • tạo một mảng v
    • nếu nums [i] không được truy cập, thì dfs (nums [i], nums, v, đã truy cập)
    • ret:=tối đa của ret và kích thước là v
  • trả lời lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   void dfs(int node, vector <int>& arr, vector <int>& v, set <int>& visited){
      if(visited.count(node)) return;
      v.push_back(node);
      visited.insert(node);
      dfs(arr[node], arr, v, visited);
   }
   int arrayNesting(vector<int>& nums) {
      int ret = 0;
      int n = nums.size();
      set <int> visited;
      for(int i = 0; i < n; i++){
         vector <int> v;
         if(!visited.count(nums[i]))dfs(nums[i], nums, v, visited);
         ret = max(ret, (int)v.size());
      }
      return ret;
   }
};
main(){
   vector<int> v = {5,4,0,3,1,6,2};
   Solution ob;
   cout << (ob.arrayNesting(v));
}

Đầu vào 

[5,4,0,3,1,6,2]

Đầu ra 

4