Ciclu

Intuiția

Un lanț e un traseu care leagă două noduri mergând din vecin în vecin. Dacă traseul se închide — pleci dintr-un nod și ajungi înapoi exact în el — ai un ciclu. Imaginea mentală e un inel: un șir de noduri prinse în cerc, unde ultimul se reîntoarce la primul. Important: nu te plimbi la întâmplare înainte și înapoi pe aceeași muchie, ci faci o buclă reală.

Vezi cum funcționează

Pornește animația. Vei urmări cum se construiește ciclul 1 — 2 — 3 — 4 — 1: plecăm din nodul 1, trecem prin nodurile noi 2, 3 și 4, iar la final muchia 4—1 ne aduce înapoi exact în nodul de plecare. Până la acea ultimă muchie aveam doar un lanț; ea este cea care închide traseul și îl transformă în ciclu.

Ce este

Lucrăm pe un graf neorientat (muchiile nu au sens, le poți parcurge în ambele direcții).

Un ciclu este un lanț în care primul nod coincide cu ultimul nod. Adică un traseu de forma v0 - v1 - v2 - ... - vk - v0, unde fiecare pereche vecină e legată printr-o muchie, iar capătul se întoarce la început.

Un ciclu este elementar dacă, în afară de capetele care coincid, toate celelalte noduri sunt distincte (nu treci de două ori prin același nod intermediar). Cu alte cuvinte, e o buclă „curată”, fără bucle mai mici prinse înăuntru.

Două precizări care apar mereu la concurs:

• Lungimea unui ciclu = numărul de muchii parcurse. Ciclul 1 - 2 - 3 - 4 - 1 are 4 noduri distincte și lungimea 4 — la un ciclu, numărul de muchii coincide cu numărul de noduri distincte, pentru că bucla se închide.
• Termenul „ciclu” se folosește pe grafuri neorientate. Pe un graf orientat, unde muchiile au sens, noțiunea corespunzătoare se numește circuit — o vei întâlni într-o lecție separată.

Un graf care nu conține niciun ciclu se numește graf aciclic. Grafurile aciclice sunt „zgârcite” la muchii: un graf neorientat aciclic cu n noduri are cel mult n - 1 muchii — orice muchie în plus ar închide obligatoriu o buclă. Dacă graful aciclic este și conex, obții un arbore, cea mai importantă structură fără cicluri, studiată într-un capitol dedicat.

Cum arată

Pe graful din vizualizare există muchiile 1-2, 2-3, 3-4 și 1-4. Parcurse în ordine, formează ciclul 1 - 2 - 3 - 4 - 1:

Verifică fiecare pas: muchia 1-2 există, 2-3 există, 3-4 există, iar 4-1 închide bucla. Niciun nod intermediar nu se repetă, doar nodul de plecare 1 apare și la final — semnătura unui ciclu elementar.

În schimb, succesiunea 1 - 2 - 5 - 1 NU este ciclu pe acest graf: muchiile 1-2 și 2-5 există, dar între 5 și 1 nu există muchie, deci traseul nu se poate închide. Un ciclu are nevoie ca fiecare pas, inclusiv cel de întoarcere, să calce pe o muchie reală.

Implementare C++

Cea mai utilă întrebare practică este: există vreun ciclu în graf? Pentru un graf neorientat, răspunsul vine dintr-un DFS care reține din ce nod ai venit (nodul-părinte).

Ideea: pleci în DFS și marchezi nodurile vizitate. Când, dintr-un nod curent, dai de un vecin deja vizitat care NU este părintele de unde tocmai ai venit, înseamnă că ai găsit o a doua cale către acel nod — adică o buclă. Asta este un ciclu.

#include <iostream>
#include <vector>
using namespace std;

const int NMAX = 100005;
vector<int> vecini[NMAX];     // liste de adiacenta
bool vizitat[NMAX];

// intoarce true daca gaseste un ciclu pornind din nodul curent
bool areCiclu(int nod, int parinte) {
    vizitat[nod] = true;
    for (int vecin : vecini[nod]) {
        if (!vizitat[vecin]) {
            // nod nevizitat: continuam DFS-ul mai departe
            if (areCiclu(vecin, nod)) return true;
        } else if (vecin != parinte) {
            // vecin vizitat care NU e parintele -> muchie inapoi -> ciclu
            return true;
        }
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        vecini[a].push_back(b);   // graf neorientat: muchie in ambele sensuri
        vecini[b].push_back(a);
    }

    bool gasit = false;
    for (int i = 1; i <= n; i++) {
        // -1 = nodul de start nu are parinte
        if (!vizitat[i] && areCiclu(i, -1)) {
            gasit = true;
            break;
        }
    }

    cout << (gasit ? "DA" : "NU") << "\n";   // DA daca graful are cel putin un ciclu
    return 0;
}

Bucla din main reia DFS-ul din fiecare nod nevizitat, ca să acoperi și grafurile neconexe (mai multe componente separate). Complexitatea e O(n + m): vizitezi fiecare nod și fiecare muchie o singură dată.