E bine sa dublezi nodurile si sa faci cuplaj, iar apoi sa colorezi muchiile din cuplaj.
E rau sa pui muchie de la a->b si de la b->a, pentru ca asa cum ai zis si tu poate aparea o muchie de mai multe ori in solutie. Pentru fiecare muchie, va trebui sa ii gasesti o singura orientare si sa o bagi in graful bipartit. Daca reusesti sa orientezi muchiile astfel incat pentru fiecare nod x, exact jumate din muchiile sale incidente sunt orientate dinspre/inspre x, vei avea un cuplaj maximal => solutie. Te las pe tine sa te gandesti cum faci orientarea... ar trebui sa fie destul de usor
.