De ce contează?
Te uiți la tabela de plecări dintr-un aeroport. Fiecare rând spune un singur lucru: „zbor de la București la Cluj”. Acest rând NU îți garantează automat că există și un zbor de la Cluj la București — poate că există, poate că nu; ar fi un zbor separat, cu rândul lui în tabelă. Sensul contează. Exact așa stochezi un graf orientat: o listă de perechi, fiecare cu un punct de plecare și unul de sosire.
Ce este
Lista arcelor este analogul listei muchiilor, dar pe un graf orientat.
Stochezi graful ca o colecție de arce, fiecare fiind o pereche ordonată
(u, v) care înseamnă „există o săgeată de la u la v”, adică u -> v.
Mecanismul de stocare e identic cu cel de la lista muchiilor — un șir de
perechi de noduri. Ce se schimbă e înțelesul perechii: la muchii, (u, v)
spunea „aceste două noduri sunt legate” și era totuna cu (v, u). La arce,
perechea are coadă și vârf: primul element e nodul din care pleacă săgeata,
al doilea e nodul în care ajunge. Perechea (u, v) și perechea (v, u)
sunt două arce diferite.
Consecința practică: atunci când citești arcul u -> v, NU adaugi și
inversul v -> u — ai strica orientarea. Dacă graful chiar are săgeți în
ambele sensuri între două noduri, ele apar ca două arce separate în datele de
intrare.
Exact ce era interzis la lista muchiilor devine regulă la lista
arcelor: acolo (u, v) și (v, u) erau aceeași muchie (și n-aveai voie s-o
numeri de două ori), aici sunt două arce distincte, care pot exista
independent unul de altul. Ordinea din pereche nu mai e o convenție de
scriere — e informație.