使用tarjan缩合点。

然后，dfs寻找最长的公路。

水体。

。

。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#include<vector>

#include<map>

#include<stack>

using namespace std;

#define maxn 110000

vector<int>old[maxn];

vector<int>vec[maxn];

int dnf[maxn],low[maxn],instack[maxn];

int times,nums;

stack<int>st;

int pan[maxn];

int ru[maxn];

int vis[maxn];

int ans;

int res[maxn];

int val[maxn];

void init(int n)

{

    for(int i=0;i<=n+1;i++)

    {

        dnf[i]=low[i]=instack[i]

        =pan[i]=ru[i]=vis[i]=res[i]=val[i]=0;

        vec[i].clear();old[i].clear();

    }

    while(!st.empty())st.pop();

    times=nums=1;

}

void tarjan(int x)

{

    dnf[x]=low[x]=times++;

    instack[x]=1;

    st.push(x);

    for(int i=0;i<old[x].size();i++)

    {

        int y=old[x][i];

        if(!dnf[y])

        {

            tarjan(y);

            low[x]=min(low[x],low[y]);

        }

        else if(instack[y])

        {

            low[x]=min(low[x],dnf[y]);

        }

    }

    if(low[x]==dnf[x])

    {

        int y=-1;

        while(x!=y)

        {

            y=st.top();

            st.pop();

            instack[y]=0;

            pan[y]=nums;

            val[nums]++;

        }

        nums++;

    }

}

void dfs(int x)

{

    if(res[x])return;

    res[x]=val[x];

    for(int i=0;i<vec[x].size();i++)

    {

        int y=vec[x][i];

        dfs(y);

        res[x]=max(res[x],res[y]+val[x]);

    }

}

int main()

{

    int n,m,x,y;

    while(~scanf("%d%d",&n,&m))

    {

        init(n);

        while(m--)

        {

            scanf("%d%d",&x,&y);

            old[x].push_back(y);

        }

        for(int i=1;i<=n;i++)

            if(!dnf[i])tarjan(i);

        for(int i=1;i<=n;i++)

        {

            for(int j=0;j<old[i].size();j++)

            {

                x=pan[i];

                y=pan[old[i][j]];

                if(x==y)continue;

                vec[x].push_back(y);

                ru[y]++;

            }

        }

        ans=-1;

        for(int i=1;i<nums;i++)

        {

            if(!ru[i])

            {

                dfs(i);

                ans=max(ans,res[i]);

            }

        }

        cout<<ans<<endl;

    }

    return 0;

}