circle algorithm

1. Floyd判圈算法

1.1 算法思路

使用一个快指针和一个慢指针，一个每次前进2步，一个每次前进一步。
当两个指针相遇的时候，说明此时是存在环的，如果有一个遇到了结束节点，那么此时说明
存在环，从这个相遇节点开始，再次进行行走，最终相遇的时候慢的环所走的步数就是环的长度。
如果要求出环的起点，那么对于将一点放在相遇的节点上，一个点放回到原来的起点，那么此时两个点之间的距离是
环长度的整数倍。

1.2 代码实现

C++ version
返回开头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }
        if (!(fast && fast->next)) return NULL;
        ListNode * start = head;
        while (head != slow) {
            head = head->next;
            slow = slow->next;
        }
        return head;
    }
};

2. 并查集求解最小环

2.1 算法思路

对于两个点，可能存在两种情况

  • 两个点具有相同的祖先，那么此时环的长度为 d[a] + d[b] + 1
  • 两个点不具有相同的祖先，合并成同祖先

2.2 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int f[N], d[N], n, minn = N, last;
int fa(int x) {
    if (f[x] != x) {
        int last = f[x];
        f[x] = fa(f[x]);
        d[x] += d[last];
    }
    return f[x];
}

void check(int a, int b) {
    int x = fa(a), y = fa(b);
    if (x != y) {f[x] = y; d[a] = d[b] +1;}
    else minn = min(minn, d[a] + d[b] + 1);
}
int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; i++) f[i] = i;
   for (int i = 1; i <= n; i++) {
        int y;
        scanf("%d", &y);
        check(i, y);
   }
   printf("%d\n",minn);
}