Leetcode 第231场周赛题解

[utterances-bot]

Leetcode 第231场周赛题解 | CP Wiki

lucifer1004的CP笔记

https://cp-wiki.vercel.app/tutorial/leetcode/WC231/

[codelh7]

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

[lucifer1004]

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

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

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

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