【图论杂题】：J .bomb [Tarjan 强连通分量]

题目：

团队链接：bomb

题面：

给定$n$个点$m$条边的有向图

现在每轮取走图上若干个点，每轮取点时会连带删掉一此点为出发点的所有边到达的点。（这句话我最后加上的，要不就要花里两个小时才能看懂这极其简易的题面，，）

要求每次删点不能存在两个不同的 点$i$,$j$ 使得可

以通过有向边从点 $i$到达点 $j$

求：最少多少次可以删完所有点
范围：$n,m<=1e6$

样例：

输入：

10 10
3 4
5 4
7 1
6 5
6 4
7 4
1 7
5 8
1 2
9 10

输出：

3

题解：

（这个题好不容易才参透的题面，花了我将进两个小时，还去询问了简化题目的老师，，，结果，，只说题解，，不说题意，，不唠了，上题解）
如果图中没有环的话，那答案就是最长链，但是，如果有环的话，就是tarjan求一下强连通分量然后转化成链就好，这样子转化，最后还是求最长链即可。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=1e6+7;
struct see{
    int x,ver,edge,next;}e[sea];
vector<int>v[sea];
int n,m,tot,ans,st,cnt,deep,last[sea],id[sea],dfn[sea],low[sea],sta[sea],g[sea];
void add(int x,int y){
    e[++tot].ver=y;e[tot].next=last[x];last[x]=tot;}
void tarjan(int x)
{
    dfn[x]=low[x]=++deep; sta[++st]=x;for(int i=last[x];i;i=e[i].next){
    int y=e[i].ver;if(!dfn[y]) tarjan(y),low[x]=min(low[y],low[x]);else if(!id[y]) low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){
    id[x]=++cnt; v[cnt].push_back(x);while(sta[st]^x) v[cnt].push_back(sta[st]),id[sta[st--]]=cnt;--st;}
}
int main()
{
    n=read(); m=read();for(int i=1;i<=m;i++){
    int x,y;x=read(); y=read(); add(x,y);}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);for(int x=1;x<=cnt;x++){
    for(int j=0,u;j<v[x].size();j++){
    for(int i=last[u=v[x][j]];i;i=e[i].next){
    int y=e[i].ver;if(id[y]^x) g[x]=max(g[id[y]],g[x]); }}ans=max(ans,g[x]+=v[x].size());}printf("%d\n",ans);return 0;
}

Continue……