[NOIP2015]信息传递

题义抽象出来就是一道用并查集维护最小环的题。

我们在这里除了一个并查集数组外,还开了一个环距离数组,可不进行初始化,在最后面的结果加一即可。

相较于传统并查集的写法,我们这里还要维护其父链的长度。每次找到环更新一次答案。

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

const int MAXN = 200001;

int n;
int uni[MAXN];
int dist[MAXN];
int ans = 0x8F8F8F;

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

    int father = uni[x];
    uni[x] = find(uni[x]);
    dist[x] += dist[father];

    return uni[x];
}

void solve(int a, int b) {
    int u = find(a);
    int v = find(b);

    if ( u != v ) {
        uni[u] = v;
        dist[a] = dist[b] + 1;
    } else {
        ans = min(ans, dist[a] + dist[b] + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n;

    for ( int i = 1; i <= n; ++i )
        uni[i] = i;

    int cur;
    for ( int i = 1; i <= n; ++i ) {
        cin >> cur;

        solve(i, cur);
    }

    cout << ans << endl;

    return 0;
}
阿里云服务器
Last modification:July 26th, 2019 at 08:42 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment