题解：P2661 [NOIP2015 提高组] 信息传递

Qfaiser · 2025-01-02 23:11:24 · 题解

solution

题意就是求有向图中的最小环。可以用并查集处理环。

假设建立一条 a 到 b 的有向边时，更新 a 祖先结点，若两点祖先相同则说明有环，环的大小是两点到祖先结点的距离和加一，距离边找祖先边处理即可。

code

#include<bits/stdc++.h>
using namespace std;
int n, fa[200005], ans=0x3f3f3f, cnt;
int find(int x){
    ++cnt;
    return (fa[x]==x?x:find(fa[x]));
}
int main(){
    cin >> n;
    for(int i=1; i<=n; i++)
        fa[i]=i;
    for(int i=1, t; i<=n; cnt=0, i++)
        cin >> t,
        find(t)==i?ans=min(ans, cnt):fa[i]=t;
    cout << ans;
    return 0;
}