We present a contraction-based algorithm for computing the strongly connected components of large graphs. While the worst-case complexity of the algorithm can be terrible (essentially the cost of running a DFS-based internal-memory algorithm on the entire graph), our experiments confirm that the algorithm performs remarkably well in practice. The strongest competitor is the algorithm by Sibeyn et al. , which is based on a semi-external DFS algorithm developed in the same paper. Our algorithm substantially outperforms the algorithm of  on most of the graphs used in our experiments and never performs worse. It thus demonstrates that graph contraction, which is the most important technique for solving connectivity problems on
graphs I/O-efficiently, can be used to solve such problems also on
graphs, at least as a heuristic.