DAG -descrierea solutiei
Vlad Tudose
Prima observatie pe care o facem este ca putem cauta binar solutia. Sa presupunem ca avem fixata o limita superioara L pentru gradul exterior al nodurilor 
grafului orientat rezultat in urma transformarii muchiilor in arce. Vrem sa verificam daca se poate construi un graf orientat care sa respecte aceasta
limita. Un astfel de graf va avea cel putin un nod cu gradul interior 0 (altfel graful ar avea circuite). Fie x un astfel de nod. Acest nod va avea gradul
exterior cel mult L in graful rezultat deci va avea cel mult gradul L in graful initial. Deci graful initial trebuie sa aiba cel putin un nod x cu
deg(x) <= L altfel nu se poate construi un graf care sa respecte limita superioara data de L. Daca un astfel de nod exista pentru graful initial G observam
ca G poate fi transformat intr-un graf orientat care sa respecte limita data de L daca si numai daca G - x poate fi transformat intr-un graf orientat care sa
respecte aceasta limita. Folosind aceasta observatie putem construi un algoritm care elimina pe rand nodurile x cu deg(x) <= L din graful G. Vom folosi o
coada in care vom retine nodurile ce urmeaza a fi eliminate din graf. Cand un nod x va fi eliminat se vor decrementa gradele vecinilor sai, iar daca un vecin
y ajunge sa aiba deg(y) <= L acesta va fi bagat si el in coada pentru a fi eliminat. Graful G poate fi transformat intr-un graf care sa respecte limita L
daca si numai daca prin algoritmul de mai sus se elimina toate nodurile. Acest algoritm are complexitatea O((N + M) * log(N)). Se poate imbunatati algoritmul
de mai sus observand ca nu este nevoie sa cautam binar solutia ci o putem calcula incremental. Vom elimina din graf pe rand toate nodurile in ordinea 
crescatoare a gradelor lor. Pentru aceasta vom avea n liste de noduri. A i-a lista va retine nodurile cu gradul i. Cand vom procesa lista curenta vom elimina
din ea nodurile care nu au fost deja eliminate la pasii precedenti. Cand scoatem un nod dintr-o lista vom parcurge vecinii acestui nod si pentru fiecare
vecin y vom introduce nodul y in lista deg(y) - 1 deoarece gradul nodului y a scazut cu 1. Solutia problemei noastre este data de gradul maxim al unui nod
in momentul cand acesta a fost eliminat. Ambii algoritmi obtin punctajul maxim.
