prietene

Prietene

* *d x y* – se şterge arcul de la nodul *x* la nodul *y*
* *q x y* – se doreşte răspunsul la întrebarea “Nodurile $x$ şi $y$ sunt prietene?”

h2. Cerintă

h2. Cerinţă

Date *N* , numărul de noduri, *M*, numărul de arce, cele *M* arce, *OP*, numărul de operaţii şi lista acestora, să se efectueze
operaţiile în ordinea din listă şi să se afişeze răspunsurile la operaţiile de tip *q* atunci când apar.

h2. Exemplu
table(example). |_. prietene.in |_. prietene.out |

| q 1 4

| 1
  4 5
  1 2
  2 1
  3 4
  3 2
  1 4
  9
  q 1 4

  a 4 3
  d 3 2
  q 1 4

h3. Explicaţie

La prima operaţie q 1 4 mulţimea corespunzătoare nodului 4 este mulţimea vidă iar cea corespunzătoare lui 1 este {2,4,1} - {1,4} = {2}, deci răspunsul este NO. Adăugăm arcul (4,3) şi eliminăm arcul (3,2). La următoarea operaţie q 1 4 mulţimea corespunzătoare lui 1 este {2,4,1,3} - {1,4} = {2,3} iar cea corespunzătoare lui 4 este {3,4} - {1,4} = {3}, deci răspunsul este NO. Ştergem arcul (1,4) apoi, la următoarea operaţie q 2 1 mulţimea lui 2 este
{1,2} - {1,2} = ∅ iar cea corespunzătoare lui 1 este tot {1,2} - {1,2} = ∅, deci răspunsul este YES, deoarece ambele mulţimi sunt vide.
Adăugăm arcele (4,2) şi (1,3) apoi la ultima operaţie q 1 3 mulţimea lui 1 este {1,2,3,4} - {1,3} = {2,4} iar cea corespunzătoare lui 3 este tot {1,2,3,4} - {1,3} = {2,4}, deci răspunsul este YES.

La prima operaţie q 1 4 mulţimea corespunzătoare nodului 4 este mulţimea vidă iar cea corespunzătoare lui 1 este {2,4,1} - {1,4} = {2}, deci răspunsul este NO. Adăugăm arcul (4,3) şi eliminăm arcul (3,2). La următoarea operaţie q 1 4 mulţimea corespunzătoare lui 1 este {2,4,1,3} - {1,4} = {2,3} iar cea corespunzătoare lui 4 este {3,4} - {1,4} = {3}, deci răspunsul este NO. Ştergem arcul (1,4) apoi, la următoarea operaţie q 2 1 mulţimea lui 2 este {1,2} - {1,2} = ∅ iar cea corespunzătoare lui 1 este tot {1,2} - {1,2} = ∅, deci răspunsul este YES, deoarece ambele mulţimi sunt vide.
Adăugăm arcele (4,2) şi (1,3) apoi la ultima operaţie q 1 3 mulţimea lui 1 este {1,2,3,4} - {1,3} = {2,4} iar cea corespunzătoare lui 3 este {2,3,4} - {1,3} = {2,4}, deci răspunsul este YES.
 

== include(page="template/taskfooter" task_id="prietene") ==