信息传递

洛谷-P2661-信息传递

分析

有向图的最小环问题。

实现

#include <iostream>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 200010;
int n, res = inf;
int f[N], d[N];

int find (int x) {
    if (f[x] == x) return x;

    int rt = find(f[x]);
    d[x] += d[f[x]];
    return f[x] = rt;
}
void merge (int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) {
        res = min(res, d[x] + d[y] + 1);
    } else {
        d[x] = d[y] + 1;
        f[fx] = fy;
    }
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) f[i] = i;
    for (int i = 1, to; i <= n; ++ i) {
        cin >> to; // i -> to
        merge(i, to);
    }
    cout << res << endl;
    return 0;
}