首页 > 其他分享 >图论,n^2建立边超时问题

图论,n^2建立边超时问题

时间:2022-09-25 12:11:44浏览次数:46  
标签:图论 个点 建立 复杂度 中间 超时

当出现问题要求,对左侧n个点和右侧m个点之间,全部建立边时,时间复杂度最坏是O(n^2)

可能会超时。

这是可以采用建立中间点,将左侧连接到中间点,再将中间点连向右侧。

这样建边的复杂度会降到O(n)

例题:

https://www.acwing.com/problem/content/description/458/

标签:图论,个点,建立,复杂度,中间,超时
From: https://www.cnblogs.com/ydUESTC/p/16727608.html

相关文章