Maximum Length of the Loop | tech::interview
int ret = 0;
vector<bool> visited(arr.size(), false);
vector<int> length(arr.size(), 0);
function<void(int,int)> dfs = [&] (int id, int len) {
if(visited[id]) {
ret = std::max(ret, len - length[id]); //\\
return;
}
visited[id] = true;
length[id] = len;
dfs(arr[id], len + 1);
};
for(int i = 0; i < arr.size(); ++i) dfs(i,0);
return ret >= 2 ? ret : 0;
}
Read full article from Maximum Length of the Loop | tech::interview
Given an array
Indexes0 1 2 3 4
Values3 2 1 4 0
Values are the next index of the jump0 -> 3 -> 4 -> 0...1 -> 2 -> 1...
Write a function to detect if there are loops. If yes, get the max length of the loop possible, otherwise just return zero.
G家题，实际上就是有向图找最大环。POJ有类似题。用一个DFS走一遍就好，用两个数组，一个记录visited，一个记录走过的长度。
int max_length(const vector<int>& arr) {int ret = 0;
vector<bool> visited(arr.size(), false);
vector<int> length(arr.size(), 0);
function<void(int,int)> dfs = [&] (int id, int len) {
if(visited[id]) {
ret = std::max(ret, len - length[id]); //\\
return;
}
visited[id] = true;
length[id] = len;
dfs(arr[id], len + 1);
};
for(int i = 0; i < arr.size(); ++i) dfs(i,0);
return ret >= 2 ? ret : 0;
}
Read full article from Maximum Length of the Loop | tech::interview
