BZOJ5450: 轰炸（水题，Tarjan缩点求最长路）

5450: 轰炸

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 43  Solved:18
[Submit][Status][Discuss]

Description

有n座城市，城市之间建立了m条有向的地下通道。你需要发起若干轮轰炸，每轮可以轰炸任意多个城市。但每次轰

炸的城市中，不能存在两个不同的城市i,j满足可以通过地道从城市i到达城市j。你需要求出最少需要多少轮可以

对每座城市都进行至少一次轰炸。

Input

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

n,m<=1000000。

Output

一行一个整数表示答案。

Sample Input

5 4
1 2
2 3
3 1
4 5

Sample Output

3

思路：不同的链不会相互影响，所以可以同时炸，显然时间只取决于最长的有向链。我们缩点，然后找最长路即可。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int Laxt[maxn],Next[maxn],To[maxn],cnt,scc_cnt,head;

int instk[maxn],q[maxn],dfn[maxn],low[maxn],scc[maxn],times;

vector<int>G[maxn]; int sz[maxn],dis[maxn],ind[maxn],ans;

void read(int &x){

    x=; char c=getchar();

    while(c>''||c<'') c=getchar();

    while(c>=''&&c<='') x=x*+c-'',c=getchar();

}

void add(int u,int v){

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;

}

void tarjan(int u)

{

    instk[u]=; q[++head]=u;

    dfn[u]=low[u]=++times;

    for(int i=Laxt[u];i;i=Next[i]){

        int v=To[i];

        if(!dfn[v]) {

            tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else if(instk[v])low[u]=min(low[u],dfn[v]);//无向图与有向图的区别

    }

    if(dfn[u]==low[u]){

        scc_cnt++;

        while(true){

             int x=q[head--];

             scc[x]=scc_cnt; instk[x]=; sz[scc_cnt]++;

             if(x==u) break;

        }

    }

}

int main()

{

    int N,M,u,v; scanf("%d%d",&N,&M);

    rep(i,,M) read(u),read(v),add(u,v);

    rep(i,,N) if(!dfn[i]) tarjan(i);

    rep(i,,N){

        for(int j=Laxt[i];j;j=Next[j]){

            if(scc[i]!=scc[To[j]]){

                ind[scc[To[j]]]++;

                G[scc[i]].push_back(scc[To[j]]);

            }

        }

    }

    head=; int tail=;

    rep(i,,scc_cnt) if(!ind[i]) q[++head]=i,dis[i]=sz[i];

    while(tail<head){

        int u=q[++tail];

        ans=max(ans,dis[u]); int L=G[u].size();

        for(int i=;i<L;i++){

            int v=G[u][i]; ind[v]--;

            dis[v]=max(dis[v],dis[u]+sz[v]);

            if(!ind[v]) q[++head]=v;

        }

    }

    printf("%d\n",ans);

    return ;

}