#include #include int n; // Počet vrcholov int **strom; int *pnasl; // Počty následníkov int *parovanie; int vysledok; void postorder(int vrchol) { int volny = -1; // Prechádzame strom metódou postorder for (int i = 0; i < pnasl[vrchol]; i++) { postorder(strom[vrchol][i]); if (parovanie[strom[vrchol][i]] == 0) // Našli sme nejaký voľný vrchol volny = strom[vrchol][i]; } if (volny >= 0) { // Aktuálny a voľný vrchol pridáme do párovania parovanie[volny] = 1; parovanie[vrchol] = 1; vysledok++; } } int main() { // Vstup int koren; scanf("%d", &n); strom = (int **) malloc(n * sizeof(int *)); pnasl = (int *) malloc(n * sizeof(int)); parovanie = (int *) malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { int k; scanf("%d", &k); // Načítame počet následníkov vrchola i pnasl[i] = k; strom[i] = (int *) malloc(n * sizeof(int)); for (int j = 0; j < pnasl[i]; j++) { int nasl; scanf("%d", &nasl); strom[i][j] = nasl; // Následníkov si zapamätáme v poli strom } } scanf("%d", &koren); // Inicializácia vysledok = 0; for (int i = 0; i < n; i++) parovanie[i] = 0; postorder(koren); printf("%d\n", vysledok); return 0; }