洛谷 P2661. 信息传递

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, p[N], dis[N], ans = 1e9;

int find(int x) {
    if (p[x] != x) {
        int last = p[x];
        p[x] = find(p[x]);
        dis[x] += dis[last];
    }

    return p[x];
}

void merge(int x, int y) {
    int px = find(x);
    int py = find(y);

    if (px != py) {
        p[px] = py;
        dis[x] += dis[y] + 1;
    } else {
        ans = min(ans, dis[x] + dis[y] + 1);
    }
}

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

    cout << ans << endl;

    return 0;
}