求证明图论问题 & 复杂度
查看原帖
求证明图论问题 & 复杂度
397329
To_our_starry_sea楼主2024/9/26 22:49

已知有 nn 个点,mm 条边的无向连通图。第 ii 条边记作 (ui,vi)(u_i, v_i)。设 f(i)f(i) 表示最大的 jj,使得 (uj,vj)(u_j, v_j)(ui1,vi1)(u_{i - 1}, v_{i - 1}) 构成的子图中 uiu_iviv_i 在同一联通快中(若不存在则为 11),求证:i=1m(if(i)+1)\sum\limits_{i = 1}^m (i - f(i) + 1)O(nm)O(nm) 级别。

thx!

2024/9/26 22:49
加载中...