Здравствуйте, C-D.

Задача поставлена так, что никто толком ответить не сможет.

Во-первых, графы бывают разные — ориентированные, взвешенные, мультиграфы, с крашенными ребрами и вершинами.
Во-вторых, существует уйма способов представления графов — матрицами смежности и инцидентности, списками ребер и т. д.

Кроме того, еще можно понять сложность поиска циклов, — но петель? Что сложного в поиске петель?