Luvut 1,2,\dots,n ovat aluksi jokainen omassa joukossaan. Tehtäväsi on toteuttaa luokka, jossa voi yhdistää kaksi joukkoa sekä hakea suurimman joukon koon.

Voit olettaa, että n on enintään 10^5 ja luokan metodeita kutsutaan enintään 10^5 kertaa.

Python

Toteuta tiedostoon maxset.py luokka MaxSet, jossa on seuraavat metodit:

• konstruktori, jolle annetaan lukujen määrä
• merge yhdistää joukot, joissa on luvut a ja b (jos ne ovat eri joukoissa)
• get_max ilmoittaa suurimman joukon koon

class MaxSet:
    def __init__(self,n):
        # TODO

    def merge(self,a,b):
        # TODO

    def get_max(self):
        # TODO

if __name__ == "__main__":
    m = MaxSet(5)
    print(m.get_max()) # 1
    m.merge(1,2)
    m.merge(3,4)
    m.merge(3,5)
    print(m.get_max()) # 3
    m.merge(1,5)
    print(m.get_max()) # 5

Java

Toteuta tiedostoon MaxSet.java luokka MaxSet, jossa on seuraavat metodit:

• konstruktori, jolle annetaan lukujen määrä
• merge yhdistää joukot, joissa on luvut a ja b (jos ne ovat eri joukoissa)
• getMax ilmoittaa suurimman joukon koon

public class MaxSet {
    public MaxSet(int n) {
        // TODO
    }

    public void merge(int a, int b) {
        // TODO
    }

    public int getMax() {
        // TODO
    }

    public static void main(String[] args) {
        MaxSet m = new MaxSet(5);
        System.out.println(m.getMax()); // 1
        m.merge(1,2);
        m.merge(3,4);
        m.merge(3,5);
        System.out.println(m.getMax()); // 3
        m.merge(1,5);
        System.out.println(m.getMax()); // 5
    }
}