title: How to find a triangle inside a graph?
body: <p>Here is an exercise in the <a href="http://www.algorist.com/">Algorithm Design Manual</a>.</p>
  
  <blockquote>
    <p>Consider the problem of determining whether a given undirected graph G
    = (V, E) contains a triangle or cycle of length 3.</p>
    
    <p>(a) Give an O(|V |^3) to find a triangle if one exists. </p>
    
    <p>(b) Improve
    your algorithm to run in time O(|V |·|E|). You may assume |V | ≤ |E|.</p>
    
    <p>Observe that these bounds gives you time to convert between the
    adjacency matrix and adjacency list representations of G.</p>
  </blockquote>
  
  <p>Here is my thoughts:</p>
  
  <p>(a) If the graph is given as an adjacency list, I can convert the list to matrix by O(|V|^2). then I do:</p>
  
  <pre><code>for (int i = 0;i &lt; n;i++) 
     for (int j = i+1;j &lt; n;j++) 
     if (matrix[i][j] == 1) 
        for (int k = j+1;k &lt; n;k++) 
           if (matrix[i][k] == 1 &amp;&amp; matrix[j][k] == 1)
               return true;
  </code></pre>
  
  <p>This should give a O(|V|^3) to test the triangle.</p>
  
  <p>(b) My first intuitive is that if the graph is given as an adjacency list, then I will do a bfs. Whenever a cross edge is found, for example, <code>if y-x is a cross edge</code>, then i will <code>check whether parent[y] == parent[x], if true, then a triangle is found</code>.</p>
  
  <p>Could anyone tell me whether my thinking is correct or not?</p>
  
  <p>Also for this (b), I am not sure its complexity. Should it be O(|V| + |E|), right?</p>
  
  <p>How can I do it in O(|V|*|E|)?</p>