lucifer1004 / cp-wiki

lucifer1004 的 CP 笔记

https://cp-wiki.vercel.app

131 stars 14 forks source link

Open utterances-bot opened 3 years ago

utterances-bot commented 3 years ago

Leetcode 第231场周赛题解 | CP Wiki

lucifer1004的CP笔记

codelh7 commented 3 years ago

想请教下大佬，21-28行的时间复杂度怎么计算的呀？看上去套了三重循环，不太会分析呀

lucifer1004 commented 3 years ago

@codelh7 注意所有的groups[i]最多有N个元素，所以最内层循环的执行次数最多是N次。

这种分析就类似于图的遍历：

for (int u = 0; u < n; ++u) {
  for (int v : adj[u]) {
    // do something...
  }
}

看上去是两层循环，实际上内层执行的总次数为O(E)次。