Author: lllyouo
Date: 20250330
tag: 基环树
link: https://www.acwing.com/problem/content/361/

问题描述

link

分析

略

参考代码

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

const int N = 1e6 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int dfn[N], a[N], f[N][2], fa[N], num;
long long ans;
bool vis[N];
int n, root, broken;

void add(int a, int b) {
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}

void get_cycle(int x, int y, int i) {
    if (a[x] == y) root = x; // x -> y
    else root = y;
    broken = i;
}

void dfs(int x) {
    dfn[x] = ++ num;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (!dfn[y]) {
            fa[y] = i;
            dfs(y);
        } else if ((i ^ 1) != fa[x] && dfn[y] >= dfn[x]) { // 考虑自环
            get_cycle(x, y, i);
        }
    }
}

void dp(int x, int times) {
    f[x][0] = f[x][1] = 0;
    vis[x] = true;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (!vis[y] && i != broken && (i ^ 1) != broken) {
            dp(y, times);
            f[x][0] += max(f[y][0], f[y][1]);
        }
    }
    
    if (times == 2 && x == a[root]) {
        f[x][1] = f[x][0] + 1;
    } else {
        for (int i = h[x]; i != -1; i = ne[i]) {
            int y = e[i];
            if (!vis[y] && i != broken && (i ^ 1) != broken) {
                f[x][1] = max(f[x][1], f[y][0] + f[x][0] - max(f[y][0], f[y][1]) + 1);
            }
        }
    }
    vis[x] = false;
}

int main() {
    memset(h, -1, sizeof h);
    idx = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        add(i, a[i]); add(a[i], i);
    }
    
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            dfs(i);
            
            dp(root, 1);
            int t = max(f[root][0], f[root][1]);
            dp(root, 2);
            t = max(t, f[root][0]);
            ans += t;
        }
    }
    printf("%lld\n", ans);
    
    return 0;
}