SSL2840 2017年11月7日提高组T2 轰炸（tarjan+拓扑）

2017年11月7日提高组T2 轰炸

Description

战狂也在玩《魔方王国》。他只会征兵而不会建城市，因此他决定对小奇的城市进行轰炸。
小奇有n 座城市，城市之间建立了m 条有向的地下通道。战狂会发起若干轮轰炸，每轮可以轰炸任意多个城市。
每座城市里都有战狂部署的间谍，在城市遭遇轰炸时，它们会通过地下通道撤离至其它城市。非常不幸的是，在地道里无法得知其它城市是否被轰炸，如果存在两个不同的城市i，j，它们在同一轮被轰炸，并且可以通过地道从城市i 到达城市j，那么城市i 的间谍可能因为撤离到城市j 而被炸死。为了避免这一情况，战狂不会在同一轮轰炸城市i 和城市j。
你需要求出战狂最少需要多少轮可以对每座城市都进行至少一次轰炸。

Input

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

Output

输出一行仅一个整数表示答案。

Sample Input

5 4
1 2
2 3
3 1
4 5
Sample Output

3
Hint

对于20%的数据，n,m<=10。
对于40%的数据，n,m<=1000。
对于另外30%的数据，保证无环。
100%的数据，n,m<=1000000。

分析：显然是求最长链，但是有环怎么搞，把环变成一个点即可，用tarjan缩点，最后拓扑求最长链。

代码

#include <cstdio>
#include <queue>
#define N 1000005
using namespace std;

struct arr
{
    int from,to,nxt;
}a[N],b[N];
queue<int> q;
int ls[N],s[N][3],w[N],f[N],in[N],n,m,l,o,ans;
int dfn[N],low[N],p[N],ls1[N],stack[N],stac,cnt,x;
bool v[N];

void add(int x,int y)
{
    a[++l].to=y;
    a[l].from=x;
    a[l].nxt=ls[x];
    ls[x]=l;
}

void add1(int x,int y)
{
    b[++l].to=y;
    b[l].nxt=ls1[x];
    ls1[x]=l;
}

int max(int x,int y)
{
    return x>y?x:y;
}

void tarjan(int i)
{
    x++;
    dfn[i]=low[i]=x;
    v[i]=true;
    stack[++stac]=i;
    for (int k=ls[i];k;k=a[k].nxt)
    {
        int j=a[k].to;
        if (dfn[j]==0) 
        {
            tarjan(j);
            if (low[j]<low[i]) low[i]=low[j];
        }
        else if (v[j]&&low[i]>dfn[j]) low[i]=dfn[j];
    }
    if (dfn[i]==low[i])
    {
        cnt++;
        int j=0;
        while (i!=j)
        {
            j=stack[stac];
            stac--;
            v[j]=false;
            p[j]=cnt;
            w[cnt]++;
        }
    }
}

int main()
{
    freopen("bomb7.in","r",stdin);
// freopen("bomb.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    l=0;
    for (int i=1;i<=n;i++)
        if (dfn[i]==0) tarjan(i);
    for (int i=1;i<=n;i++)
        v[i]=false;
    for (int i=1;i<=m;i++)
        if (p[a[i].from]!=p[a[i].to])
        {
            add1(p[a[i].from],p[a[i].to]);
            in[p[a[i].to]]++;
        }
    for (int i=1;i<=n;i++)
        if(!in[i]) q.push(i);
    int ans=0;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        f[v]+=w[v];
        ans=max(ans,f[v]);
        for (int i=ls1[v];i;i=b[i].nxt)
        {
            int u=b[i].to;
            f[u]=max(f[u],f[v]);
            if(!--in[u]) q.push(u);
        }
    }
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
}