【模板】缩点

概念

在有向图中，将环上的点的信息压缩到一个点上的过程，叫做缩点。

适用范围

• 有向图
• 最大/最小问题
• 每个点只做一次贡献
• 可多次经过点

算法思路

1. 建图，并存下图的两边的点
2. Tarjan找强连通分量（环），并用环的其中一点视为整个环的标记，将图分为多个环
3. 新建图，将图中的环链接
4. topo环，从环中找到答案

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+12;
int low[N],dfn[N],id,f[N];
int h[N],head[N],cnt1,cnt,n,m,u,v;
bool vis[N];
int p[N],dis[N],in[N];
int clor[N],c,ans;
stack<int>s;
struct{    
  int from,to,nex; //边的起始和末位置
}edge[N<<2],e[N<<2];

void addedge(int u,int v)
{
  cnt++;
  edge[cnt]={ u,v,head[u] };
  head[u]=cnt;
}

void add(int u,int v)
{
  cnt1++;
  e[cnt1]={ u,v,h[u] };
  h[u]=cnt1;
}

void tarjan(int x)  //tarjan算法找环
{
  dfn[x]=low[x]=++id;
  vis[x]=1;
  s.push(x);
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( !dfn[y] )
    {
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if( vis[y]  )
    {
      low[x]=min( low[x] , dfn[y] );
    }
  }
  if( low[x]==dfn[x] )
  {
    while( s.top()!=x )
    {
      int y=s.top();
      clor[y]=x;  //用x点标记与x强连通相同的点（环）。
      p[x]+=p[y];
      s.pop();
      vis[y]=0;
    }
    clor[x]=x;
    vis[x]=0;
    s.pop();
  }
}
void topo()
{
  queue<int>q;
  for(int i=1;i<=n;i++)
  {
    if( clor[i]==i && !in[i] ) //topo排序环，只有没有入边，并且是缩点后的环才入队
    {
      q.push(i);
      dis[i]=p[i];
    }
  }
  while( !q.empty() )
  {
    int x=q.front();
    q.pop();
    for(int i=h[x];i;i=e[i].nex)
    {
      int y=e[i].to;
      in[y]--;
      dis[y]=max( dis[y],dis[x]+p[y] ); //记录答案
      if( !in[y] ) q.push(y);
    }
  }
  for(int i=1;i<=n;i++)
  {
    ans=max(ans,dis[i]);
  }
  cout<<ans<<endl;  //输出路径上的权值的最大值
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&p[i]);
  }
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d",&u,&v);
    addedge(u,v);  //存边
  }
  for(int i=1;i<=n;i++)
  {
    if( !dfn[i] )
    {
      tarjan(i);
    }
  }
  for(int i=1;i<=m;i++ )
  {
    int c1=clor[ edge[i].from ] , c2=clor[ edge[i].to ];
    if( c1!=c2 )  //如果这两个点不是在一个边上的才在新图中连接
    {
      add( c1,c2 ); //新图链接两个点
      in[c2]++;
    }
  }
  topo();

}