f********a
发帖数: 165 | 1 数组： index 0 1 2 3 4
value 3 2 1 4 0
从任意个元素开始，利用值来找到下一个元素的位置，找出最大的环。比如从
第一个元素开始：
0 -> 3 -> 4 -> 0 |
h****y
发帖数: 137 | 2 用union-find吧?
【在 f********a 的大作中提到】
: 数组： index 0 1 2 3 4
: value 3 2 1 4 0
: 从任意个元素开始，利用值来找到下一个元素的位置，找出最大的环。比如从
: 第一个元素开始：
: 0 -> 3 -> 4 -> 0
|
d***n
发帖数: 832 | 3 最大环怎么定义？
0 3 4 0
1 2 1
2 1 2
3 4 0 3
4 0 3 4 |
p*u
发帖数: 136 | 4 直接类似dfs的做法就可以了吧，记录下哪些节点已经被访问了的。找到环的时候，记
录下当前dfs的深度就是环的大小。取个最大的
【在 f********a 的大作中提到】
: 数组： index 0 1 2 3 4
: value 3 2 1 4 0
: 从任意个元素开始，利用值来找到下一个元素的位置，找出最大的环。比如从
: 第一个元素开始：
: 0 -> 3 -> 4 -> 0
|
w*******e
发帖数: 285 | 5 这就是有向图里面找最大的强连通分量吧。
【在 p*u 的大作中提到】
: 直接类似dfs的做法就可以了吧，记录下哪些节点已经被访问了的。找到环的时候，记
: 录下当前dfs的深度就是环的大小。取个最大的
|
n****e
发帖数: 678 | 6 同感
【在 p*u 的大作中提到】
: 直接类似dfs的做法就可以了吧，记录下哪些节点已经被访问了的。找到环的时候，记
: 录下当前dfs的深度就是环的大小。取个最大的
|
A***o
发帖数: 358 | 7 这个有点像代数里面的cyclic group，想清楚了在这种特殊情况下怎么测环，就几行
code。
【在 f********a 的大作中提到】
: 数组： index 0 1 2 3 4
: value 3 2 1 4 0
: 从任意个元素开始，利用值来找到下一个元素的位置，找出最大的环。比如从
: 第一个元素开始：
: 0 -> 3 -> 4 -> 0
|
i********s
发帖数: 22 | 8 value是0-(n-1)之间的么?
那直接dfs就可以了，O(N)复杂度
vector used(n, false);
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs(i, , i, arr, used, len);
if (len > max_len) {
max = len;
}
}
}
void dfs(int start, int idx, int[] arr, vector& used, int &len) {
used[idx] = true;
len ++;
if (!used[arr[idx]]) {
dfs(start, arr[idx], arr, used, len);
} else {
assert(start == idx)
}
} |
