P3387 【模板】缩点

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10,inf = 0x3f3f3f3f;// g: 原图的邻接表, e: 缩点后新图的邻接表
vector<int> g[N],e[N];// Tarjan算法相关
int dfn[N],low[N],id;    // dfn:深度优先序, low:能回溯到的最小dfn, id:时间戳计数器
int q[N],top,inq[N];     // q:模拟栈, top:栈顶, inq:标记节点是否在栈中
int n,m;// 缩点相关
int scc[N],sccnt;        // scc[i]:节点i所属的SCC编号, sccnt:SCC计数器
int sccval[N];           // sccval[i]:第i个SCC的总权值// 拓扑排序相关
ll a[N],f[N];            // a[i]:原节点权值, f[i]:以SCC i结尾的最大路径和
int rd[N];               // rd[i]:SCC i的入度// Tarjan算法求强连通分量
void tarjan(int x)
{dfn[x] = low[x] = ++id;    // 初始化当前节点的dfn和lowq[++top] = x;              // 节点入栈inq[x] = 1;                // 标记节点在栈中// 遍历所有邻接节点for(int i = 0; i < g[x].size(); i++){int y = g[x][i];if(dfn[y] == 0){        // 树边：y未被访问
            tarjan(y);low[x] = min(low[x],low[y]);  // 回溯时更新low值
        }else if(inq[y]) low[x] = min(low[x],dfn[y]);  // 回边：y在栈中
    }// 找到SCC的根节点if(low[x] == dfn[x]){sccnt++;while(1){int y = q[top--];     // 弹出栈顶节点inq[y] = 0;           // 标记不在栈中scc[y] = sccnt;       // 记录节点所属SCCsccval[sccnt] += a[y]; // 累加SCC权值if(x == y) break;     // 弹出直到遇到根节点x
        }}
}// 拓扑排序求DAG最长路径,注意拓扑排序中用的是新图e，而非g 
void topsort()
{queue<int> q;ll ans = 0;// 初始化：所有入度为0的SCC入队for(int i = 1; i <= sccnt; i++){    f[i] = sccval[i];         // 初始值为SCC自身权值if(rd[i] == 0) q.push(i); // 入度为0的入队
    }// 拓扑排序while(q.size()){int x = q.front(); q.pop();// 遍历x的所有出边for(int i = 0; i < e[x].size(); i++){int y = e[x][i];rd[y]--;  // 入度减1// 状态转移：f[y] = max(f[y], f[x] + sccval[y])f[y] = max(f[y],f[x] + sccval[y]);ans = max(ans,f[y]);  // 更新答案if(rd[y] == 0) q.push(y);  // 入度为0时入队
        }}// 确保找到最大值（处理没有入度的孤立SCC）for(int i = 1; i <= sccnt; i++) ans = max(ans,f[i]);cout << ans;
}int main()
{// 输入处理cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i];  // 读入点权for(int i = 1; i <= m; i++){int x,y; cin >> x >> y;g[x].push_back(y);  // 构建原图
    }// 步骤1: Tarjan算法求所有强连通分量for(int i = 1; i <= n; i++){if(dfn[i] == 0) tarjan(i);  // 对每个未访问节点执行Tarjan
    }// 步骤2: 构建缩点后的新图(DAG)for(int i = 1; i <= n; i++){for(int j = 0; j < g[i].size(); j++){int y = g[i][j];if(scc[i] != scc[y]){  // 不同SCC之间的边e[scc[i]].push_back(scc[y]);  // 添加新图的边rd[scc[y]]++;                 // 目标SCC入度加1
            }}}// 步骤3: 拓扑排序求最长路径
    topsort();return 0;
}