Вам задан неориентированный граф, состоящий из \(n\) вершин и \(m\) ребер. Ваша задача — найти количество компонент связности, которые являются циклами.
Вот несколько определений из теории графов.
Неориентированный граф состоит из двух множеств: множества узлов (называемых вершинами) и множества рёбер. Каждое ребро соединяет пару вершин. Все ребра двунаправленные (то есть если вершина \(a\) соединена с вершиной \(b\), вершина \(b\) тоже соединена с вершиной \(a\)). Ребро не может соединять вершину саму с собой, также не может существовать более одного ребра между парой вершин.
Две вершины \(u\) и \(v\) принадлежат одной компоненте связности тогда и только тогда, когда существует хотя бы один путь по ребрам, соединяющий \(u\) и \(v\).
Компонента связности является циклом тогда и только тогда, когда все ее вершины могут быть переупорядочены следующим образом:
- первая вершина соединена ребром со второй вершиной,
- вторая вершина соединена ребром с третьей вершиной,
- ...
- последняя вершина соединена ребром с первой вершиной,
- все описанные выше ребра цикла — различны.
Цикл содержит только вершины и ребра, описанные выше. По определению цикл содержит не менее трех вершин.
Граф на рисунке содержит \(6\) компонент связности, \(2\) из них являются циклами: \([7, 10, 16]\) и \([5, 11, 9, 15]\). Примечание
В первом тестовом примере только компонента \([3, 4, 5]\) является циклом.
Второй пример соответствует рисунку из условия.