标签：tarjan缩点，拓扑排序，DP
题目
轰炸（bomb）
【题目描述】
有n座城市，城市之间建立了m条有向的地下通道。
你需要发起若干轮轰炸，每轮可以轰炸任意多个城市。但每次轰炸的城市中，不能存在两个不同的城市i,j满足可以通过地道从城市i到达城市j。
你需要求出最少需要多少轮可以对每座城市都进行至少一次轰炸。
【输入数据】
第一行两个整数n，m。接下来m行每行两个整数a，b表示一条从a连向b的单向边。
【输出数据】
一行一个整数表示答案。
【样例输入】
5 4
1 2
2 3
3 1
4 5
【样例输出】
3
【数据范围】
对于20%的数据，n,m<=10。
对于40%的数据，n,m<=1000。
对于另外30%的数据，保证无环。
对于100%的数据，n,m<=1000000。
分析
唔，感觉这题noip难度，全世界都A了这题
先将原图tarjan缩点，重构图，转化为求最长链
容易发现将一个大小为x的强连通分量替换成一个长度为x的链，所有点两两之间的连通关系不变。
然后按拓扑序DP即可
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define newreg(x) for(int i=rlast[x];i;i=re[i].next)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e6+6,maxm=2e6+6;
int dfn[maxn],low[maxn],que[maxn<<1],d[maxn],last[maxn],rlast[maxn],time=0,top,cnt=0,tot;
int belong[maxn],v[maxn],n,m;
int f[maxn],ans=0;
bool inq[maxn];
struct edge{int to,next;}e[maxm<<1],re[maxm<<1];
queue <int> q;
void tarjan(int x){
int now=0;
dfn[x]=low[x]=++time;
que[++top]=x;inq[x]=1;
reg(x)
if(!dfn[e[i].to]){tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}
else if(inq[e[i].to])low[x]=min(low[x],dfn[e[i].to]);
if(low[x]==dfn[x]){
tot++;
while(now!=x){
now=que[top--];
belong[now]=tot;
v[tot]++;
inq[now]=0;
}
}
}
void rebuild(){
cnt=0;
rep(k,1,n)
reg(k)
if(belong[e[i].to]!=belong[k]){
re[++cnt]=(edge){belong[e[i].to],rlast[belong[k]]};rlast[belong[k]]=cnt;d[belong[e[i].to]]++;
}
}
int main()
{
n=read(),m=read();
rep(i,1,m){
int u=read(),v=read();
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
}
rep(i,1,n)if(!dfn[i])tarjan(i);//cout<<"R";
rebuild();
//rep(i,1,n)cout<<belong[i]<<' ';cout<<endl;
//rep(i,1,tot)cout<<d[i]<<' '<<v[i]<<endl;cout<<"E\n";
rep(i,1,tot)if(d[i]==0)q.push(i);
while(!q.empty()){
int now=q.front();q.pop();
f[now]+=v[now];
ans=max(ans,f[now]);
newreg(now){
f[re[i].to]=max(f[re[i].to],f[now]);
d[re[i].to]--;if(!d[re[i].to])q.push(re[i].to);
}
}
cout<<ans<<endl;
return 0;
}
