P2661 [NOIP2015 提高组] 信息传递

//用带权并查集解决

#include <iostream>
using namespace std;
int n, f[200005], d[200005];
int find(int x)
{
    if (f[x] != x)  //对d进行维护 
    {
        int root = find(f[x]);
        d[x] += d[f[x]];
        return f[x] = root;
    }
    else return x;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) f[i] = i, d[i] = 0;
    int res = 1 << 27;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        int px = find(x), py = find(i);
        if (px == py) res = min(res, d[i] + d[x] + 1);
        else f[i] = x, d[i] = 1; //只能使用朴素合并方式 
    }
    cout << res;
    return 0;
}

P2921 [USACO08DEC]Trick or Treat on the Farm G

url

#include<iostream>
#include<cstdio>
using namespace std;
int n, d[100008], s[100008], h[100008], flag;
bool vis[100008];
int dfs(int now, int nowc)
{
    if (h[now] != 0)
        return nowc - 1 + h[now];
    if (vis[now] == true)
    {
        h[now] = nowc - s[now];
        flag = now;
        return nowc - 1;
    }
    vis[now] = true;
    s[now] = nowc;
    int ans = dfs(d[now], nowc + 1);
    if (flag != 0)
    {
        if (now == flag)
            flag = 0;
        else
            h[now] = h[flag];
    }
    else
        h[now] = h[d[now]] + 1;
    vis[now] = false;
    return ans;
}
int main()
{
    scanf_s("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf_s("%d", &d[i]);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", dfs(i, 1));
    return 0;
}