Mihnea trăiește pe o planetă de dimensiunea n x n, cu linii și coloane enumerate de la 1 la n. Spunem că celula (l, c) este intersecția liniei l cu coloana c. Fiecare celulă de pe planetă este fie pământ, fie apă.

Pentru a-l ajuta pe Mihnea, intenționezi să creezi cel puțin un tunel. Tunelul îi va permite lui Mihnea să călătorească liber între cele două puncte extreme ale tunelului. Într-adevăr, crearea unui tunel este un efort mare: costul creării unui tunel între celulele (l1, c1) și (l2, c2) este (l1 – l2) ^ 2 + (c1 – c2) ^ 2.

Cerința

Pentru moment, sarcina ta este să găsești costul minim de a crea câteva tuneluri astfel încât Mihnea să poată călători de la (l1,c1) la (l2,c2). Dacă nu trebuie creat niciun tunel, costul este 0.

Date de intrare

In fisierul de intrare mihneapolis.in, prima linie conține un număr întreg n (1 ≤ n ≤ 50) — dimensiunea planetei.
A doua linie conține două numere întregi separate prin spațiu l1 și c1 (1 ≤ l1, c1 ≤ n) – indicând celula în care locuiește Mihnea.
A treia linie conține două numere întregi separate prin spațiu l2 și c2 (1 ≤ l2, c2 ≤ n) – indicând celula în care Mihnea dorește să meargă.
Fiecare dintre următoarele n linii conține un șir de n caractere. Al j-lea caracter de pe linia i reprezintă tipul de celulă de la coordonata (i, j) (1 este teren, 0 este apă).
Este garantat că (l1, c1) și (l2, c2) sunt celule de teren.

Date de ieșire

In fișierul mihneapolis.out, afișați un număr întreg care reprezintă costul minim de creare a câteva tuneluri, astfel încât Mihnea să poată călători de la (l1,c1) la (l2,c2).

Exemplu

mihneapolis.in

5
1 1
5 5
00001
11111
00111
00110
00110

mihneapolis.out

10

Problemă propusă de @My_Life_Is_Not_Life și @mateiUNU

Un graf orientat G=(V,E) este tare conex dacă pentru orice pereche de noduri distincte (x,y) există cel puțin un drum de la x la y și există cel puțin un drum de la y la x.

Pentru un graf orientat, se numește componentă tare conexă un subgraf tare conex maximal – prin adăugarea a încă unui nod, subgraful obținut nu mai este tare conex.

Exemplu

Graful de mai sus nu este tare conex. El are trei componente tare conexe.

Verificarea tare conexității. Determinarea componentelor tare conexe

Verificare tare conexității unui graf orientat poate fi privită ca un caz particular al determinării componentelor tare conexe, deoarece, dacă graful are o singură componentă tare conexă atunci el este tare conex. În continuare vom vedea două metode de determinare a componentelor tare conexe. Ambele folosesc noțiunea de graf transpus, pe care o definim în continuare:

Definiție: Fie G=(V,E) un graf orientat. Se numește graf transpus al lui G graful orientat GT=(V,ET), cu aceeași mulțimea a nodurilor și pentru orice pereche de noduri are loc: (x,y) este arc în G dacă și numai dacă (y,x) este arc în GT.

Exemplu

Graf orientat inițial	Graful orientat transpus

Să observăm că pentru două noduri oarecare x, y:

• existența unui drum de la x la y poate fi determinată cu o parcurgere (de exemplu în adâncime) în graful G, pornind din nodul x;
• existența unui drum de la y la x poate fi determinată cu o parcurgere în graful GT, pornind tot din nodul x.

Algoritmul Plus-Minus

Folosind observații de mai sus, pentru a determina componentele tare conexe folosim următorul algoritm, numit Plus-Minus:

• pentru fiecare nod x al grafului care încă nu a fost plasat într-o componentă tare conexă:
  • determinăm toate nodurile în care se poate ajunge din x, folosind graful G și le marcăm într-un tablou cu plus;
  • determinăm toate nodurile din care se poate ajunge în x, folosind graful GT și le marcăm într-un tablou cu minus;
  • nodurile marcate atât cu plus, cât și cu minus, împreună cu x formează o componentă tare conexă;

Exemplu:

Fie graful de mai sus. Să determinăm componenta tare conexă din care face parte nodul 6:

Graful inițial	Graful transpus
S-au marcat cu plus nodurile: 5 7 8	S-au marcat cu minus nodurile: 1 2 3 4 5 7 8

Nodurile marcate de două ori, 5 7 8, împreună cu nodul inițial, 6, formează o componentă tare conexă.

Secvență C++:

• n, a[][] – numărul de noduri și matricea de adiacență
• nrc – numărul de componente tare conexe
• ctc[] – tablou pentru memorarea componentelor tare conexe: ctc[i] = numărul de ordine al componentei din care face parte nodul i
• s[], p[] – tablouri pentru marcarea nodurilor vizitate în timpul parcurgerilor
• să observăm că graful inițial și cel transpus pot fi memorate prin aceeași matrice de adiacență

void df1(int x)
{
    s[x] = 1;
    for(int i =1 ; i <= n ; i ++)
        if(s[i] == 0 && a[x][i] == 1)
            df1(i);
}

void df2(int x)
{
    p[x] = 1;
    for(int i =1 ; i <= n ; i ++)
        if(p[i] == 0 && a[i][x] == 1)
            df2(i);
}

int main()
{
    .....
    for(int i = 1 ; i <= n ; ++i)
        if(ctc[i] == 0)
        {
            for(int j = 1; j <= n ; ++j)
                s[j] = p[j] = 0;
            nrc ++;
            df1(i); df2(i);
            for(int j = 1; j <= n ; ++j)
                if(s[j] == 1 && p[j] == 1)
                    ctc[j] = nrc;
        }
    ....
}

Algoritmul lui Kosaraju

Alt algoritm, mai eficient, pentru determinarea componentelor tare conexe este Algoritmul lui Kosaraju.

Să ne amintim că la parcurgerea în adâncime se pot asocia nodurilor două momente de timp:

• d[x] – momentul când nodul x este descoperit și adăugat pe stivă: timpul de descoperire a nodului
• f[x] – momentul când se termină de vizitat succesorii lui x, iar nodul x se elimină de pe stivă: timpul de finalizare a nodului

Aceste momente de timp vor fi numere naturale între 1 și 2*n, unde n este numărul de noduri din graf.

Algoritmul lui Kosaraju este:

• determinăm graful transpus GT
• parcurgem în adâncime graful și determinăm pentru fiecare nod x timpul de finalizare f[x]
• parcurgem în adâncime graful transpus GT, dar considerăm nodurile în ordinea descrescătoarea timpilor de finalizare
• nodurile din arborii de parcurgere obținuți reprezintă câte o componentă tare conexă

Exemplu:

Graf orientat inițial	Graful orientat transpus

În urma parcurgerii în adâncime a grafului inițial G nodurile în ordinea finalizării sunt:

Parcurgem graful transpus GT analizând nodurile în ordinea inversă a timpilor de finalizare:

• începem cu nodul 1; se vizitează nodurile 3 4; se determină componenta tare conexă {1,3,4};
• continuăm cu nodul 2 (nodurile 1, 3 și 4 au fost vizitate mai devreme); nu se vizitează alte noduri; se determină componenta tare conexă {2};
• continuăm cu nodul 5; se vizitează nodurile 6 8 7; se determină componenta tare conexă {5, 6, 7, 8}.

Secvență C++:

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<vector<int> > G, GT;

int n , m , contor , nrs;

vector<bool> V;
vector<int> S;

void read()
{
    cin >> n >> m;
    G = GT = vector<vector<int>>(n + 1);
    for(int i = 1 ; i <= m ; i++)
    {
        int a , b;
        cin >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }

}

void dfs(int k)
{
    V[k] = true;
    for(auto x : G[k])
        if(!V[x]) 
            dfs(x);
    S.push_back(k);
}

void dfsGT(int k)
{
    V[k]=1;
    for(auto x: GT[k])
        if(! V[x])
            dfsGT(x);

}

int main()
{
    read();

    V = vector<bool> (n + 1, false);
    for(int i = 1 ; i <= n ; i ++)
        if(! V[i]) 
            dfs(i);

    V = vector<bool> (n + 1, false);
    for(vector<int>::reverse_iterator it = S.rbegin() ; it != S.rend() ; it ++)
        if(!V[*it]) {
                contor ++;
                dfsGT(*it);
        }

    cout<<contor;
    return 0;
}

Complexitatea acestui algoritm este aceea a parcurgerii în adâncime: O(n2) dacă memorăm graful prin matricea de adiacență, O(n+m) dacă memorăm graful prin liste de adiacență.

Fie G=(V,E) un graf neorientat conex:

• un nod al grafului se numește punct de articulație sau nod critic dacă subgraful obținut prin eliminarea lui nu este conex;
• o muchie se numește punte sau muchie critică dacă graful parțial obținut prin eliminarea ei nu este conex;
• un graf neorientat se numește biconex dacă nu conține puncte de articulație;
• se numește componentă biconexă un subgraf biconex maximal – prin adăugarea încă unui nod nu mai este biconex.

Exemplu:

Graful inițial	Puncte de articulație	Punți	Componente biconexe

Câteva observații:

• pentru fiecare muchie critică, cel puțin o extremitate este punct de articulație;
• fiecare punct de articulație face parte din cel puțin două componente biconexe;
• nodurile care fac parte dintr-un ciclu aparțin aceleiași componente biconexe;
• fiecare muchie critică reprezintă ea însăși o componentă biconexă;
• o muchie este critică dacă nu face parte dintr-un ciclu;

Pentru a determina punctele de articulație și punțile se poate folosi un algoritm naiv, bazat pe eliminarea succesivă a câte unui nod (muchie) și verificarea conexității. Complexitatea acestor algoritmi este O(n*C), respectiv O(m*C), unde O(C) este complexitatea algoritmului de verificarea a conexității (O(n*n) dacă reprezentăm graful prin matrice de adiacență, O(n+m) dacă reprezentăm graful prin liste de adiacențe).

În cele ce urmează vom prezentat un algoritm bazat pe parcurgerea în adâncime a grafului. Complexitatea sa este aceeași cu a parcurgerii în adâncime.

Considerăm G=(V,E) graful dat și A arborele de parcurgere în adâncime. Reamintim că muchiile graful pot fi doar:

• muchii de parcurgere, folosite la înaintarea în arbore
• muchii de întoarcere; o muchie (k,x) este de întoarcere dacă x este ascendent al lui k în arborele A – nodul x a fost descoperit anterior nodului k

Pentru graful de mai sus, arborele de parcurgere este următorul – muchiile de parcurgere sunt desenate cu linii continue, cele de întoarcere cu linii întrerupte.

Observăm următoarele:

• un nod k al grafului, diferit de rădăcina arborelui DFS, este punct de articulație dacă și numai dacă are un descendent direct x în arborele A cu proprietatea că de la niciun descendent al lui x sau de la x nu există muchie de întoarcere la niciun ascendent al lui k;
• rădăcina arborelui DFS este punct de articulație dacă și numai dacă are în acest arbore cel puțin doi descendenți direcți.

Pentru a determina punctele de articulație, punțile și componentele biconexe vom determina pentru fiecare nod k următoarele informații:

• nivel[k] – nivelul pe care se află nodul k în arborele DFS;
  • nivel[rădăcină] = 1;
  • nivel[k] = nivel[tata[k]] + 1;
• nma[k] – nivelul minim la care se poate ajunge din k, mergând numai pe muchii de arbore și folosind ca ultimă muchie o muchie de întoarcere. Îl vom numi nivelul minim accesibil și este egal cu minimul dintre următoarele 3 valori :
  • nivelul nodului curent
  • minimul dintre nivelurile nodurilor cu care este legat nodul curent printr-o muchie de întoarcere
  • minimul dintre nivelurile minime accesibile ale fiilor nodului curent din cadrul arborelui DFS

Pentru graful de mai sus aceste valori sunt următoarele:

Cu ajutorul acestor valori, un nod k care nu este rădăcina arborelui este punct de articulație dacă și numai dacă are cel puțin un fiu x pentru care nivelul minim accesibil este mai mare sau egal cu nivelul nodului (nivel[k] <= nma[x]). Să analizăm nodurile:

• 1 nu este punct de articulație, deoarece este rădăcina arborelui și are un singur descendent direct
• 2 este punct de articulație, deoarece 3 este fiu al lui 2 și nivel[2] <= nma[3]
• 3 nu este punct de articulație, deoarece nu are niciun fiu
• 4 nu este punct de articulație, deoarece nu are niciun fiu
• 5 este punct de articulație deoarece 7 este fiu al lui 5 și nivel[5] <= nma[7]
• 6 nu este punct de articulație; pentru singurul fiu al lui 6, 8 relația este nivel[6] > nma[8]
• 7 este punct de articulație deoarece 6 este fiu al lui 7 și nivel[7] <= nma[6]
• 8 nu este punct de articulație deoarece nu are fii

Fie (k,x) o muchie de arbore, în care k este tatăl lui x. Această muchie este critică dacă și numai dacă (nivel[k] < nma[x]). Muchiile de întoarcere nu sunt niciodată muchii critice, deoarece aparțin întotdeauna unor cicluri.

Cele două șiruri de valori se construiesc în timpul parcurgerii DFS. Fie k nodul curent în parcurgerea DFS:

• stabilim nivel[k] = nivel[tata[k]] + 1 – această valoare va rămâne neschimbată până la final;
• inițializăm nma[k] = nivel[k]
• parcurgem nodurile adiacente cu k. Fie x un asemenea nod:
  • dacă x a fost deja parcurs și nu este tatăl lui k, muchia (k,x) este muchie de întoarcere. Dacă este cazul actualizăm nma[k] la valoarea nivel[x] (dacă nivel[x] este mai mic decât valoarea actuală a lui nma[k]);
  • dacă x nu a fost încă parcurs, continuăm parcurgerea din x – îl adăugăm pe stivă/apel recursiv. La eliminarea de pe stivă/ revenirea din autoapel, actualizăm valoarea nma[k] la valoarea nma[x] (dacă nma[k] este mai mare decât nma[x], acesta din urmă este calculat deja)

Următorul pseudocod descrie cum se calculează pentru fiecare nod al grafului nivelul și nivelul minim accesibil, folosind parcurgerea în adâncime:

subprogram DFS(k, tata)
    V[k] ← true
    nivel[k] ← nivel[tata] + 1
    nma[k] ← nivel[k]
    pentru x - nod adiacent cu k
        dacă x ≠ tata
            dacă V[x] = true atunci
                dacă nma[k] > nivel[x] atunci
                    nma[k] ← nivel[x]
                sf_dacă
            altfel
                DFS(x,k)
                dacă nma[k] > nma[x] atunci
                    nma[k] ← nma[x]
                sf_dacă

                // determinare puncte de articulație

                // determinare punți

                // determinare componente biconexe

            sf_dacă
        sf_dacă
    sf_pentru
sf_subprogram

Pentru a determina punctele de articulație:

• la eliminarea de pe stivă a nodului x (revenirea din autoapel) verificăm dacă acest și nodul părinte k verifică relația nivel[k] <= nma[x]; în caz afirmativ, decidem că nodul k este critic;
• pentru a stabili dacă rădăcina este punct de articulație trebuie să-i numărăm descendenții direcți în arbore.
• Observație: un punct de articulație poate fi descoperit de mai multe ori – dacă există mai mulți fii ai săi care respectă relația de mai sus.

//determinare puncte de articulație
dacă nivel[k] ≤ nma[x] și nod ≠ rădăcină atunci
    //nodul k este punct de articulație
sf_dacă

Pentru a determina punțile:

• la eliminare de pe stivă a nodului x/revenirea din autoapel vom determina muchiile de parcurgere (k,x) pentru care nivelul lui k este mai mic decât nivelul minim accesibil al lui x: nivel[k] < nma[x].

//determinare punți
dacă nivel[k] < nma[x] atunci
    //muchia (k,x) este punte
sf_dacă

Pentru a determina componentele biconexe:

• utilizăm o stivă suplimentară S, pe care adaugăm noduri la vizitarea lor conform parcurgerii și le eliminăm la determinarea unei componente biconexe;
  • ordinea nodurilor din stiva S este cea a parcurgerii în adâncime;
• dacă pentru nodul curent k avem un descendent direct x pentru care nivel[k] <= nma[x], vom elimina de pe stivă nodurile până la nodul x, inclusiv acesta;
  • nodurile eliminate, împreună cu nodul k reprezintă o componentă biconexă;
  • eliminarea se face până la x, nu până la k, deoarece între acestea, pe stivă, pot fi noduri din altă componentă biconexă.
• Observație: condiția nivel[k] <= nma[x] are loc întotdeauna pentru rădăcina arborelui DFS, chiar dacă acesta nu este punct de articulație. În acest caz se determină o componentă biconexă din care face rădăcina. Acest lucru se întâmplă și când graful dat este biconex: determinarea componentei biconexe se face la revenirea în rădăcină.

...
V[k] ← true
Adaugă(S,k)
....
//determinare componente biconexe
dacă nivel[x] ≤ nma[k] atunci
    câttimp Vârf(S) ≠ x execută
        Vârf(S) se adugă la componenta curentă
        Elimină(S)
    sf_câttimp
    x se adaugă la componenta curentă
    Elimină(S)
    k se adaugă la componenta curentă
sf_dacă

Introducere

În 1736, matematicianul elvețian Leonard Euler a rezolvat o problemă cunoscută astăzi ca “Problema celor șapte poduri din Königsberg”. Prin orașul Königsberg, azi Kaliningrad trece un râu pe care sunt două insule, acestea și malurile fiind unite prin poduri ca în imaginea de mai jos.

Leonard Euler a demonstrat că nu este posibil ca o persoană să traverseze fiecare pod o singură dată. În onoarea sa, o categorie specială de grafuri se numesc grafuri euleriene.

Definiții

• Într-un graf neorientat, se numește lanț eulerian un lanț simplu în care apare fiecare muchie (fiind lanț simplu, fiecare muchie apare o singură dată).
• Într-un graf neorientat, se numește ciclu eulerian un ciclu în care apare fiecare muchie.
• Un graf neorientat se numește graf eulerian dacă conține un ciclu eulerian.

Exemplu

În graful de mai sus ciclul (1 2 4 5 3 6 5 2 3 1) este eulerian.

Teorema de caracterizare

Un graf neorientat fără vârfuri izolate este eulerian dacă și numai dacă este conex și toate vârfurile au grad par.
Un graf neorientat fără vârfuri izolate conține un lanț eulerian, dacă și numai dacă este conex și toate vârfurile au grad par, mai puțin două. Aceste vârfuri vor fi extremitățile lanțului eulerian.

Determinarea unui ciclu eulerian

Pentru determinarea unui ciclu eulerian se pot folosi mai mulți algoritmi. Unul dintre aceștia este asemănător cu parcurgerea în adâncime. Vom folosi o stivă (eventual memoria STACK prin intermediul recursivității):

• adăugăm pe stivă un vârf oarecare – de exemplu 1;
• cât timp stiva nu este vidă
  • fie k – nodul din vârful stivei
  • determinăm nodurile x adiacente cu k. Eliminăm muchia [k,x] și adăugăm nodul x pe stivă (apel recursiv)
    • continuăm cu nodul situat în vârful stivei
  • adăugăm nodul k într-o listă
  • eliminăm nodul k din stivă
• lista construită reprezintă ciclu eulerian

Important:

• la vizitarea unui vârf, acesta nu va fi marcat, pentru a permite revenirea în el;
• finitudinea algoritmului este asigurată de faptul că muchiile se elimină din graf;

Secvență C++:

Considerăm un graf cu n vârfuri, memorat prin intermediul matricei de adiacență, A[][]. Tabloul L[] reprezintă lista în care se memorează ciclul eulerian. Toate variabilele sunt globale:

void Euler(int k)
{
	for(int i = 1 ; i <= n ; i ++)
		if(A[k][i] == 1)
		{
			A[k][i] = A[i][k] = 0;
			Euler(i);
		}
	L[++p] = k;
}
...
Euler(1);
...

Algoritmul de mai sus poate fi utilizat și pentru determinarea unui lanț eulerian. Parcurgerea trebuie să înceapă însă din unul dintre vârfurile cu grad impar.

Puzzle-uri

Există numeroase puzzle-uri care constau în desenarea unei figuri fără a lua creionul de pe foaie și fără a trece de mai multe ori pe aceiași linie. Probabil cel mai cunoscut este “plicul”:

Care dintre următoarele figuri se pot desena în cest mod? Cum?

Prin parcurgerea unui graf neorientat se înţelege examinarea în mod sistematic a vârfurilor, plecând dintr-un vârf dat start, astfel încât fiecare vârf accesibil din start pe muchii incidente două câte două să fie vizitat o singură dată. Trecerea de la un vârf x la altul se face prin examinarea, într-o anumită ordine a vecinilor săi.

Parcurgerile grafurilor sunt frecvent utilizate în rezolvarea multor probleme. Animația de mai jos, (preluată de aici) prezintă modul în care se parcurge un labirint folosind mecanisul parcurgerii în adâncime.