bzoj5450 轰炸

传送门

分析

不难想到如果这个图是一个DAG则答案就是图的最长路

于是我们考虑有环的情况

我们发现一个环上的所有点颜色一定不相同

于是我们发现答案就是缩点之后跑一遍点权最长路

点权就是这个强联通分量中的点的数量

注意求最长路的时候要用拓扑排序求

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

vector<int>v[],nv[];

int n,m,dfn[],low[],ist[],sum,cnt;

int belong[],d[],w[],du[],vis[];

stack<int>a;

queue<int>q;

inline void tarjan(int x){

    dfn[x]=low[x]=++cnt;

    a.push(x);

    ist[x]=;

    for(int i=;i<v[x].size();i++)

      if(!dfn[v[x][i]]){

          tarjan(v[x][i]);

          low[x]=min(low[x],low[v[x][i]]);

      }else if(ist[v[x][i]]){

        low[x]=min(low[x],dfn[v[x][i]]);

      }

    if(dfn[x]==low[x]){

      sum++;

      while(){

          int u=a.top();

          a.pop();

          ist[u]=;

          belong[u]=sum;

          w[sum]++;

          if(u==x)break;

      }

    }

}

int main(){

    int i,j,k;

    scanf("%d%d",&n,&m);

    for(i=;i<=m;i++){

      int x,y;

      scanf("%d%d",&x,&y);

      v[x].push_back(y);

    }

    for(i=;i<=n;i++)

      if(!dfn[i])tarjan(i);

    for(i=;i<=n;i++)

      for(j=;j<v[i].size();j++)

        if(belong[i]!=belong[v[i][j]])

          nv[belong[i]].push_back(belong[v[i][j]]),

          du[belong[v[i][j]]]++;

    for(i=;i<=sum;i++)

      if(!du[i]){

          d[i]=w[i];

          q.push(i);

      }

    while(!q.empty()){

      int x=q.front();

      q.pop();

      for(i=;i<nv[x].size();i++)

        if(du[nv[x][i]]){

          du[nv[x][i]]--;

          d[nv[x][i]]=max(d[nv[x][i]],d[x]+w[nv[x][i]]);

          if(!du[nv[x][i]])q.push(nv[x][i]);

        }

    }

    int Ans=;

    for(i=;i<=sum;i++)Ans=max(Ans,d[i]);

    cout<<Ans;

    return ;

}