In: Computer Science
In this program, the user will enter some permutation of the integers 0 to n-1, inclusive, (each integer in that range will appear exactly once) followed by -1 to indicate the end of the input. The user will never input more than 100 numbers. Your job is to store all the numbers in an array in the order they are input. For example if the user inputs 3 0 2 1 -1 then you should store the 3 at index 0 in an array, 0 at index 1, 2 and index 2, and 1 at index 3. Once you have stored the data in your array your task is to find the maximum length cycle in the array. To answer the question, "What does cycle mean?", interpret the value at index i as the next index in the array that we should visit. So in the example above, at index 0 is the value 3. This indicates that we should go visit index 3 of the array next. Once we go to index 3 we find the value 1. This tells us to go visit index 1 next. Once we go to index 1 we find the value 0. This tell us to go visit index 0 next. But we've already visited index 0 (it's where we started). If and when you get back to your starting location (i.e. we started at location 0 and then got back to that location because the value at index 1 told us to go to 0) we stop and define those indices to be a cycle. So in this case the cycle is created from index 0 3 1 (and then back to 0). This cycle has a length of 3 since it tooks us 3 steps to get back to the starting location. Your job is to detect the longest (max number of steps to get back to the starting point) cycle in the array. Notice, once we start at 0 and find a cycle of length 3, we could then repeat the process starting at index 1. As we start at index 1 we would visit 0, from 0 we would go to 3, and from 3 back to 1. The same cycle is detected and thus its length is the same. We have not found anything longer. From there we could look for a cycle starting at location 2. At index 2 we find the value 2 which tells us to simply stay put (or go back to itself). Thus, we have a cycle of length 1 since 2 only requires one step before we get back to the starting point. By doing this cycle-walking process starting at each point in the array we can determine the longest cycle.
Note: You may realize there is some inefficiency in what we've described. We would find the cycle of 0 3 1 three times as we start our search from 0, then from 1, and finally from 3. You can potentially use another array to avoid this duplicated work, but you are not required to do so. It is fine to use an "inefficient" approach to solve this problem.
Your program should only output a single number on the last line of output which should be the length of the longest cycle present in the array.
Example 1
If the user entered:
3 0 2 1 -1
Your program should output exactly the lines:
3
Example 2
If the user entered:
1 2 3 4 0 -1
Your program should output exactly the lines:
5
Example 3
If the user entered:
0 1 2 3 4 -1
Your program should output exactly the lines:
1
Example 3
If the user entered:
1 0 3 4 2 -1
Your program should output exactly the lines:
3
I really need help and the language is C++
To solve this question we need to use a depth-first search (DFS) function that will visit each array and check if it is visited or not. The get_longest_cycle() method returns the maximum length of the cycle by checking each cycle and updating the value of the max. The main() function is used to take input from user till it enters -1 and to print out the final max_length.
The necessary comments that will help you understand the solution.
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
// DFS method
void dfs(int start, int idx, int a[], int N, bool *visited, int &len)
{
if (idx >= N)
{
len = 1;
return;
}
visited[idx] = true;
len++;
if (visited[a[idx]] == false)
{
dfs(start, a[idx], a, N, visited, len);
}
else if (start == idx)
return;
}
// Function to get the maximum length of the cycle
int get_longest_cycle(int a[], int N)
{
int maxlen = -1;
bool *visited = new bool[N];
for (int i = 0; i < N; i++)
visited[i] = false;
for (int i = 0; i < N; i++)
{
if (visited[i] == false)
{
int len = 0;
dfs(i, a[i], a, N, visited, len);
maxlen = max(maxlen, len);
}
}
return maxlen;
}
// Driver Function
int main()
{
vector<int> v1;
cout << "Start Entering the numbers in array(Enter -1 to stop)" << endl;
for (int i = 0; i < 100; i++)
{
int input;
cin >> input;
if (input != -1)
{
//-1 condition check
v1.push_back(input);
}
else
{
break;
}
}
int size = v1.size();
int a[size];
for (int i = 0; i < size; i++)
{
a[i] = v1[i];
}
// Output of the max:length;
cout << get_longest_cycle(a, size);
return 0;
}
I hope you have understood
the solution. If you like the solution kindly upvote
it.