/**
 *   Løsning til eksamen i AlgMet, august 2025, oppgave 2.
 *
 *   @file     EX_S25_2.TXT
 *   @author   Frode Haug, NTNU
 */



OPPGAVE A:
==========

    Keyene:            S   T   R   U   T   S   E   K   L   O
    k (alfabetnr):     19  20  18  21  20  19  5   11  12  15
    Hash1 (M = 13):     6   7   5   8   7   6  5   11  12   2
    Hash2:              1   4   2   3   4   1   3   1   4   1

    Indeksene:          0   1   2   3   4   5   6   7   8   9  10  11  12
                        -   -   -   -   -   -   S   -   -   -   -   -   -
                        -   -   -   -   -   -   S   T   -   -   -   -   -
                        -   -   -   -   -   R   S   T   -   -   -   -   -
                        -   -   -   -   -   R   S   T   U   -   -   -   -
                        -   -   -   -   -   R   S   T   U   -   -   T*  -
                        -   -   -   -   -   R   S   T   U   S*  -   T*  -
                        -   E*  -   -   -   R   S   T   U   S*  -   T*  -
                        -   E*  -   -   -   R   S   T   U   S*  -   T*  K*
                        -   E*  -   L*  -   R   S   T   U   S*  -   T*  K*
                        -   E*  O   L*  -   R   S   T   U   S*  -   T*  K*

                        (* = bokstaver som hashes på plass ved bruk av hash2 også.)





OPPGAVE B:
==========

    Fringen etterhvert (NVd = Nodenavn, Vekt, dad):

                              D-1a   H-1d
                       A-1e   B-2a   B-2a   G-1h          F-1b
                       G-2e   G-2e   G-2e   B-2a   B-2a   I-2b   I-1f
                  E*   C-2e   C-2e   C-2e   C-2e   C-2e   C-2e   C-2e   C-2e



    Minimums spenntreet:       B --- F --- I
                              / 
                             A ----- D
                            /        |
                           E -- C    H
                                    /
                                   G





OPPGAVE C:
==========

    "gForeldre"-arrayen etterhvert:

            A  B  C  D  E
    A B:    -  A  -  -  -
    E B:    E  A  -  -  -
    C B:    E  E  -  -  C     Path Compression
    D A:    C  E  D  -  C     Path Compression
    D B:    C  D  D  -  D     Path Compression





       Resulterende skog:      D
                             / | \ 
                            B  C  E
                               |
                               A