why not bool array? because the size is unknown? c++ solution: #include #include using namespace std; int findCycle(int idx[], int size){ deque visited(size, false); int max = 1; for (int i = 0; i < size; ++i) { if (!visited[i]) { visited[i] = true; int cnt = 1; for (int j = idx[i]; j!=i; j = idx[j]) { visited[j] = true; cnt++; } if (cnt > max) max = cnt; } } return max; } int main(){ int idx [] = {3, 2, 1, 4, 0}; cout << findCycle (idx, 5) << endl; }
贴个in-place的解吧: int find_cycle(vector& A) { int max = 0; for(int i = 0; i < A.size(); ++ i) { if (A[i] != i) { int len = 0; while(A[i] != i) { int temp = A[i]; A[i] = A[temp]; A[temp] = temp; len ++; } max = std::max(max, len); } } return max; }
why not bool array? because the size is unknown? c++ solution: #include #include using namespace std; int findCycle(int idx[], int size){ deque visited(size, false); int max = 1; for (int i = 0; i < size; ++i) { if (!visited[i]) { visited[i] = true; int cnt = 1; for (int j = idx[i]; j!=i; j = idx[j]) { visited[j] = true; cnt++; } if (cnt > max) max = cnt; } } return max; } int main(){ int idx [] = {3, 2, 1, 4, 0}; cout << findCycle (idx, 5) << endl; }
贴个in-place的解吧: int find_cycle(vector& A) { int max = 0; for(int i = 0; i < A.size(); ++ i) { if (A[i] != i) { int len = 0; while(A[i] != i) { int temp = A[i]; A[i] = A[temp]; A[temp] = temp; len ++; } max = std::max(max, len); } } return max; }