Pro přirozené číslo m uvažujeme množinu X = {0, 1, ..., m − 1}. Binární relaci R na množině X můžeme reprezentovat jako matici s m řádky a m sloupci (řádky a sloupce jsou číslovány od 0) následujícím způsobem: pokud (i, j) ∈ R, je na řádku i ve sloupci j hodnota 1, jinak je tam hodnota 0.
Matici lze v programu zachytit pomocí pole tak, jak jsme si ukázali na semináři. Pole má velikost m ⋅ m, hodnota matice na řádku i ve sloupci j se nachází na indexu i ⋅ m + j.
Naprogramujte funkce:
int equivalence(int r[], int m);
void transitive_closure(int r[], int m);Funkce equivalence oveří jestli je relace reprezentovaná
polem r ekvivalencí. Funkce transitive_closure
upraví r na její tranzitivní uzávěr. Argument
m u obou funkcí má význam velikosti množiny X (tedy velikost r je
m*m).
Za první funkci lze získat 2 body, za druhou funkci 1 bod.