CodeForces - 615B Best beautiful——简单dp

CodeForces - 615B Best beautiful——简单dp

#include #include #include #include #include using namespace std;typedef long long ll;const int maxn = 1e5 + 10;int n, m;ll du[maxn], dp[maxn];vector g[maxn];void dfs(int u) { if (dp[u]) return; ll temp = 0; for (unsigned int i = 0; i < g[u].size(); i++) { int v = g[u][i]; dfs(v); temp = max(temp, dp[v]); } dp[u] = temp + 1;}int main() { scanf("%d %d", &n, &m); int u, v; memset(du, 0, sizeof(du)); for (int i = 1; i <= m; i++) { scanf("%d %d", &u, &v); if (u < v) swap(u, v); du[u]++; du[v]++; g[u].push_back(v); } memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) dfs(i); ll ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, dp[i] * du[i]); } printf("%lld\n", ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。