struct Tarjan:Graph{//强连通分量缩点 int low[maxn],dfn[maxn],belong[maxn],stk[maxn],instk[maxn],block[maxn]; int step,color; void tarjan(){ step=color=0; for(int i=0;i<=n;i++) dfn[i]=0; for(int i=1;i<=n;i++) if(dfn[i]==0) tarjan(i,0);//多个联通快 } void tarjan(int u,int father=0){//此函数不开放 low[u]=dfn[u]=++step; stk[++stk[0]]=u;instk[u]=1; for(int i=head[u];~i;i=edge[i].nex){ int v=edge[i].v; if(dfn[v]) { if(instk[v]) low[u]=min(low[u],dfn[v]); } else{ tarjan(v,u); low[u]=min(low[u],low[v]); } } if(low[u]==dfn[u]){ block[color+1]=1; while(stk[stk[0]]!=u) { belong[stk[stk[0]]]=color+1; instk[stk[stk[0]--]]=0; block[color+1]++; } belong[stk[stk[0]]]=++color; instk[stk[stk[0]--]]=0; } } void rebuild(Dag&dag){ set<long long>se; dag.ini(color); for(int u=1;u<=n;u++){ int uu=belong[u]; for(int i=head[u];~i;i=edge[i].nex){ int v=edge[i].v; int vv=belong[v]; if(uu==vv||se.find(uu*1e6+vv)!=se.end())continue; se.insert(uu*1e6+vv); dag.add_edge(uu,vv); } dag.dp[uu][u]=1; dag.w[uu]=block[uu]; } } }graph;