Longtail Hedgehog

一个水题,先统计下每个点的度数,然后维护一个数组表示到这个点的最大长度是多少.然后拿ans更新就好.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>v[N];
int dp[N],deg[N];
int main()
{
    int n,m;//n个点 m条边
    long long ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);  
        v[y].push_back(x);
        deg[x]++;deg[y]++;
    }                   
    for(int i=1;i<=n;i++) dp[i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            int x=v[i][j];
            if(x>i) dp[x]=max(dp[x],dp[i]+1);
        }
    }
    for(int i=1;i<=n;i++) ans=max(ans,(long long)dp[i]*deg[i]);
    printf("%lld\n",ans);
    return 0;
}