使用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;
}
版权声明：本文博主原创文章。博客，未经同意不得转载。