轰炸（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。
首先，如果图中无环的话，答案就是图中最长链的点数。
我们从两个方面来证明这个答案的正确性：
1. 因为最长链上一次最多轰炸一个点，所以答案肯定>=最长链的长度。
2.设f[i]为从i开始的最长链长度，那么我们就在第i轮轰炸所有f[x]==i的x城市。因为同一条链上的f值肯定都不相同，所以这样肯定合法。所以答案<=最长链长度。
然后就证明了答案就是最长链的点数。
那么有环的话怎么办？？
因为一个强联通分量中的点都是可以互达的，所以我们可以缩点之后把点权设置为这个点中原图的点的数量，然后这个图的最长链(路径上点权和最大的路径)就是答案。
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define pb push_back
using namespace std;
int s[maxn],tp=0;
int lt[maxn],f[maxn];
int to[maxn],ne[maxn];
int hd[maxn],num=0,n,m;
int siz[maxn],k=0,dc=0;
int dfn[maxn],low[maxn];
vector<int> g[maxn];
inline int read(){
int x=0; char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}
void dfs(int x){
dfn[x]=low[x]=++dc;
s[++tp]=x;
for(int i=hd[x];i;i=ne[i])
if(!dfn[to[i]]){
dfs(to[i]);
low[x]=min(low[x],low[to[i]]);
}
else if(!lt[to[i]]) low[x]=min(low[x],dfn[to[i]]);
if(low[x]==dfn[x]){
k++;
for(;;){
lt[s[tp]]=k,siz[k]++;
if(s[tp--]==x) break;
}
}
}
inline void tarjan(){
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
int S,T;
for(int i=1;i<=n;i++){
S=lt[i];
for(int j=hd[i];j;j=ne[j]){
T=lt[to[j]];
if(S!=T) g[S].pb(T);
}
}
}
int dp(int x){
if(f[x]) return f[x];
int to;
for(int i=g[x].size()-1;i>=0;i--){
to=g[x][i];
f[x]=max(f[x],dp(to));
}
f[x]+=siz[x];
return f[x];
}
int main(){
freopen("bomb.in","r",stdin);
freopen("bomb.out","w",stdout);
int uu,vv;
n=read(),m=read();
for(int i=1;i<=m;i++){
uu=read(),vv=read();
to[i]=vv,ne[i]=hd[uu],hd[uu]=i;
}
tarjan();
int ans=0;
for(int i=1;i<=k;i++) ans=max(ans,dp(i));
printf("%d
",ans);
return 0;
}