NOIP模拟赛 轰炸（bomb）

题目描述

有$n$座城市，城市之间建立了$m$条有向的地下通道。

你需要发起若干轮轰炸，每轮可以轰炸任意多的城市。但在每次轰炸城市中，不能同时存在两个城市$i,j$满足可以通过地下通道从城市$i$到达城市$j$。你需要求出最少需要多少轮可以对每座城市都进行至少一次轰炸。

输入格式

第一行一个整数$m$，接下来$m$行每行两个整数$a,b$表示一条从$a$到$b$的单向边。

输出格式

一行一个整数表示答案。

样例输入

5 4
1 2
2 3
3 1
4 5

样例输出

3

数据范围

$1\le n,m\le 10^6$

题解

题意即为每次可以轰炸任意多的城市，但不能有两个城市$i,j$满足$i,j$在同一条链上。

如果这个图没有环，那么显然答案为最长的一条链。这条链上每个点都轰炸一次。与此同时，其他链上的点也都轰炸一次，即可将所有城市都轰炸一次。用拓扑排序即可解决。

那如果有环呢？我们可以用求强连通分量的Tarjan算法，求出每个强连通分量，再把每个强连通分量都缩成一个点。此时的图已经没有环了，按上面的方法做就行了。

注意缩点之后，炸完一个点所需要的次数为这个点表示的强连通分量的大小。

时间复杂度为$O(n)$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int n,m,x,y,tot=0,dt=0,top=0,ans=0,d[N+5],l[N+5],r[N+5],st[N+5];
int ct=0,dfn[N+5],low[N+5],c[N+5],cnt[N+5],f[N+5];
vector<int>hv[N+5];
queue<int>q;
struct node{int x,y;
}w[N+5];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs(int u){dfn[u]=low[u]=++dt;st[++top]=u;for(int i=r[u];i;i=l[i]){int v=d[i];if(!dfn[v]){dfs(v);low[u]=min(low[u],low[v]);}else if(!c[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){++ct;while(top>0){c[st[top]]=ct;hv[ct].push_back(st[top]);--top;if(st[top+1]==u) break;}}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);w[i]=(node){x,y};add(x,y);}for(int i=1;i<=n;i++){if(!dfn[i]) dfs(i);}tot=0;memset(r,0,sizeof(r));for(int i=1;i<=m;i++){x=w[i].x;y=w[i].y;if(c[x]==c[y]) continue;add(c[x],c[y]);++cnt[c[y]];}for(int i=1;i<=ct;i++){if(!cnt[i]) q.push(i);}while(!q.empty()){int u=q.front();q.pop();f[u]+=hv[u].size();for(int i=r[u];i;i=l[i]){f[d[i]]=max(f[d[i]],f[u]);--cnt[d[i]];if(!cnt[d[i]]) q.push(d[i]);}}for(int i=1;i<=ct;i++){ans=max(ans,f[i]);}printf("%d",ans);return 0;
}