C++(g++ 7.5.0) 解法, 执行用时: 292ms, 内存消耗: 138484K, 提交时间: 2023-04-11 20:14:18

#include<iostream>
#include<queue>
#include<cstring>
#include<stack>
using namespace std;
const int N=1e6+10;
int n,m,ans,a[N],b[N];
int h[N],e[N],ne[N],idx;
int dfn[N],low[N],timestamp;
int sp_id[N],sum[N],sp_idx,f[N];
stack<int> stk;
bool in_stk[N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk.push(u),in_stk[u]=true;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u]){
        int y;
        sp_idx++;
        do{
            y=stk.top();
            stk.pop();
            in_stk[y]=false;
            sp_id[y]=sp_idx;
            sum[sp_idx]++;
        }while(y!=u);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a[i],&b[i]);
        add(a[i],b[i]);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=m;i++){
        int ia=sp_id[a[i]],ib=sp_id[b[i]];
        if(ia!=ib) add(ia,ib);
    }
    for(int i=1;i<=sp_idx;i++) f[i]=sum[i];
    for(int i=sp_idx;i;i--){
        for(int j=h[i];j!=-1;j=ne[j]){
            int k=e[j];
            f[k]=max(f[k],f[i]+sum[k]);
        }
    }
    for(int i=1;i<=sp_idx;i++) ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

C++ 解法, 执行用时: 432ms, 内存消耗: 196976K, 提交时间: 2021-11-03 21:57:41

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int dfn[N];
int dp[N]; 
vector<int>v[N];
vector<int>v2[N];
int low[N];
int timestamp;
int stk[N];
int id[N];
int cnt;
bool in_stk[N];
int top;
int n,m;
int sz[N];
void tarjin(int u){
	dfn[u]=low[u]=++timestamp;
	stk[++top]=u;
	in_stk[u]=true;
	for(auto j:v[u])
	{
		if(!dfn[j])
		{
			tarjin(j);
			low[u]=min(low[u],low[j]);
		}
		else if(in_stk[j])
		{
			low[u]=min(low[u],dfn[j]);
		}
	}
	if(low[u]==dfn[u])
	{
		int y;
		++cnt;
		do{
			++sz[cnt];
			y=stk[top--];
			in_stk[y]=false;
			id[y]=cnt;
			
		}while(y!=u);
	}
}
int main(){
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
//		v[b].push_back(a);
	}
	for(int i=1;i<=n;i++)	if(!dfn[i])	tarjin(i);
	for(int i=1;i<=n;i++)
	{
		for(auto j:v[i])
		{
			if(id[i]!=id[j])
			{
				v2[id[i]].push_back(id[j]);
				
			}
		}
	}
	int res=0;
	for(int i=1;i<=cnt;i++)	dp[i]=sz[i]; 
	for(int i=cnt;i>=1;i--){
		for(auto j:v2[i])
		{
			dp[j]=max(dp[j],dp[i]+sz[j]);
			
		}
		res=max(res,dp[i]);
	}
	cout<<res;
}