P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm - Tarjan+拓扑DP

传送门

tarjan缩点后进行拓扑dp求出从点i出发的最大点权和，由于是dfs遍历，所以相当于从终点走到点i的最大点权和。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=100000+100,M=500000+100;
inline void r(int &x){
    x=0;
    char ch=getchar();
    bool f=0;
    while(!isdigit(ch)) f=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    if(f) x=-x;
}
struct node{
    int to,nxt;
}e[M];
int head[N],tot;
inline void add(int u,int v){
    e[++tot]=(node){v,head[u]};
    head[u]=tot;
}
int dfn[N],low[N],idx;
int s[N],top;
bool ins[N];
int col[N],colv[N],cnt;
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    s[++top]=u;
    ins[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        cnt++;
        while(s[top]!=u){
            ins[s[top]]=0;
            col[s[top]]=cnt;
            colv[cnt]++;
            top--;
        }
        ins[u]=0;
        col[u]=cnt;
        colv[cnt]++;
        top--;
    }
}
struct ed{
    int u,v;
}E[M];
int in[N];
int dp[N];
int dfs(int u){
    if(dp[u]) return dp[u];
    dp[u]=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        dp[u]=max(dp[u],dfs(v));    
    }
    dp[u]+=colv[u];
    return dp[u];
}
int main(){
    int n;
    r(n);
    for(int i=1;i<=n;i++){
        int v;
        r(v);
        add(i,v);
        E[i]=(ed){i,v};
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
    tot=0;
    for(int i=1;i<=n;i++){
        int u=E[i].u,v=E[i].v;
        if(col[u]!=col[v]) add(col[u],col[v]),in[col[v]]++;
    }
    for(int i=1;i<=cnt;i++) if(!in[i]) dfs(i);
    for(int i=1;i<=n;i++)
        printf("%d\n",dp[col[i]]);
    return 0;
}