In this talk we show how analyzing basic Depth First Search algorithm leads to a simple proof of the two most classical results about random graphs: 1. The result of Erdos-Renyi that the random graph $G(n,p)$ experiences sharp phase transition around $p=1/n$. For $p=(1-\epsilon)/n$, all connected components of $G(n,p)$ are typically of size $O(\log n)$, while for $p=(1+\epsilon)/n$, with high probability there exists a connected component of size linear in n. 2. The result of Ajtai-Komlos-Szemeredi that in the supercritical regime $p=(1+\epsilon)/n$, random graph typically contains a path of linear length. Joint work with M. Krivelelvich