[Problem proposal] Triangle detection

[koba-e964]

Problem name: Triangle detection
Problem ID: triangle_detection

Problem

単純無向グラフが与えられる
3 頂点であってどの組も互いに結ばれているものを一つ見つけるか、ないことを報告せよ

類題: #442

Constraint

• $1 \leq N, M \leq 10^5$
• 与えられるグラフは単純

Solution / Reference

https://www.researchgate.net/publication/220618165_Finding_a_Minimum_Circuit_in_a_Graph の方法で $O(M^{3/2})$

(Optional) Input

N M
u_0 v_0
: 
u_{M-1}, v_{M-1}

(Optional) Output

Yes
a b c

or

No

[yosupo06]

https://judge.yosupo.jp/problem/enumerate_triangles ?

検出だけならもっといい計算量あるんでしょうか

[koba-e964]

数えるのも $O^*(M^{3/2})$ でできたんですね…。
close します