Problema cere bineinteles aflarea componentelor tare conexe ale unui graf
orientat.
   Cand am propus problema, am facut-o pentru ca am considerat ca are
un algoritm foarte simplu si foarte eficient de rezolvare, (pe care am
remarcat ca multi dintre voi nu il stiu), dar se pare ca nu asta a fost
principala voastra problema. Problema spinoasa se pare ca a fost
gestionarea memoriei. Nu cred ca s-a scris vreodata pe aceasta lista de
atatea ori SC (system crash)!:-)
   Ce erori concrete a presupus SC ?

   1.Heap overflow error: acest caz a fost cel mai intalnit. Am ramas un pic
     -------------------
uimit de faptul ca nici unul dintre voi nu si-a calculat cum trebuie spatiul
de memorie necesar. Ideea este ca, dupa definirea unei structuri dinamice,
trebuie facut un calcul exact al numarului maxim de alocari posibile a
structurii respective si in caz ca acest numar "acopera" si limita maxima
impusa de problema, totul este ok, daca nu inseamna ca structura nu este bine
aleasa.

   2.Stack overflow error: aceasta eroare a aparut fie in cazul alocarii
   --------------------
statice a datelor (cam greu sa incapa in 64K, nu ?), fie in cazul in care
parcurgerea grafului s-a facut recursiv. In general, la date de asemenea
dimensiuni nu se face parcurgere recursiva, deoarece in cazul cel mai
defavorabil (in cazul de fata, o singura componenta tare conexa), cam
da eroare :-)

   3.Blocarea efectiva a calculatorului: No comment !
     ----------------------------------

   Stiu ca problema nu v-a placut foarte mult (tocmai din cauza datelor de
intrare foarte mari), dar din pacate aceste probleme sunt foarte intalnite
la concursurile de programare (si nu numai), asa ca trebuie sa stii sa
lucrezi si cu pointeri...
   In cazul de fata, folosirea matricei de adiacenta era absolut imposibila,
asa ca ramanea de ales intre liste de vecini si lista de muchii. Eu am
preferat in rezolvare varianta cu lista de vecini. Lista de muchii necesita
folosirea unor structuri auxiliare pentru ca algoritmul sa ramana linear.

   Acum pe scurt algoritmul de rezolvare:
   Nu stiu daca a folosit cineva un algoritm linear (avand in vedere
problema cu memoria, nu stiu daca s-a mai gresit si la algoritm), dar tind
sa cred ca da, pentru ca pe multe teste destul de mari, problema mergea
foarte repede, in multe cazuri.
   Algoritmul este deci absolut banal si se numeste "algoritmul plus-minus":
   
   - pentru fiecare nod neincadrat inca intr-o componenta conexa:
      - toate nodurile care intra in nodul respectiv (direct sau prin
        intermediul altor noduri) se eticheteaza cu +), iar toate nodurile
        care ies din nodul respectiv (direct sau prin intermediul altor
        noduri) se eticheteaza cu -.
      - in final nodurile etichetate si cu + si cu - apartin aceleasi
        componente tare conexe.

   Simplu, nu ?

   Trimit atasata rezolvarea mea. Nu stiu daca este foarte clara, dar nu am
acum timp sa mai comentez si sursa (deh, unii sunt in vacanta si altii in
sesiune :-) ).
   Testele nu le pot trimite, fiind mult prea mari.

                                        Va urez toate cele bune,
                                                        Cristian Cadar

   P.S. Am remarcat si prezenta unei eleve din clasa a 9-a printre
   rezolvitori (s-ar putea sa mai fi fost si alti elevi de a 9-a,
   dar numai in sursa respectiva era precizata clasa).
        Ma bucur ca si elevi din clase mai mici trimit rezolvari,
   deoarece consider ca se poate invata din orice problema. Totusi
   problema a fost mult prea grea pentru clasa a 9-a. De aceea, dau
   ca tema de documentare pentru "cei mici": reprezentarea grafurilor
   prin liste de vecini si prin lista de muchii, si determinarea
   componentelor conexe ale unui graf neorientat de dimensiuni foarte
   mari.