记忆化数组记录从这个点的最长下降序列,然后乘以这个点的度,就是ans,维护即可。
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int maxn = 1e5+;
const int maxm = 4e5+;
int N,M; struct Edge{
int to,next;
}edge[maxm]; int NE,head[maxn],mem[maxn],chd[maxn];
long long ans; int add_edge(int u,int v)
{
edge[NE].to = v;
edge[NE].next = head[u];
head[u] = NE++;
chd[u]++; edge[NE].to = u;
edge[NE].next = head[v];
head[v] = NE++;
chd[v]++;
} long long dfs(int u)
{
if(mem[u] != -) {ans = max((long long)chd[u]*mem[u],ans);return mem[u];}
mem[u] = ;
for(int i=head[u];~i;i=edge[i].next)
{
int v = edge[i].to;
if(v > u) continue;
mem[u] = max((long long)mem[u],dfs(v)+);
} ans = max((long long)mem[u] * chd[u],ans);
return mem[u];
} int main()
{
scanf("%d%d",&N,&M);
memset(head,-,sizeof head);
memset(mem,-,sizeof mem); for(int i=,u,v;i<M;i++)
{
scanf("%d%d",&u,&v);
add_edge(u,v);
} for(int i=;i<=N;i++) dfs(i); printf("%I64d\n",ans);
}