算法

(并查集)

题目大意：找出有向图的最小环
题解：使用并查集判断是否构成环，如果构成就求出它的大小，环的长度为到父亲结点上的点数（边数+1）。

C++ 代码

#include <iostream>

using namespace std;

const int N = 2e5 + 10;

int n, cnt, ans = 1e9;
int p[N];

int find(int x) {
    ++cnt; // 记录遇到了多少个节点，如果形成了环，就是环的长度
    if (p[x] == x) return x;
    return find(p[x]); // 不带路径压缩 
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) p[i] = i;

    for (int i = 1, x; i <= n; ++i) { // 判断每一个节点 
        cin >> x;
        cnt = 0; // 记得每次都清0
        if (find(x) == i) // 如果形成环
            ans = min(ans, cnt);
        else p[i] = x; // 不构成环就把边连上 
    }

    cout << ans << '\n';

    return 0;
}