CSES - Väritys Verkossa on $n$ solmua ja se on aluksi tyhjä. Tehtäväsi on toteuttaa luokka, jonka avulla pystyy lisäämään kaaren verkkoon sekä tutkimaan, voiko solmut värittää kahdella värillä niin, että jokainen kaari yhdistää kaksi eriväristä solmua.

Voit olettaa, että solmuja on enintään $50$ ja luokan metodeita kutsutaan enintään $100$ kertaa.

Python

Toteuta tiedostoon coloring.py luokka Coloring, jossa on seuraavat metodit:
  • konstruktori, jolle annetaan solmujen määrä
  • add_edge lisää kaaren kahden solmun välille
  • check tarkastaa, voiko verkon värittää kahdella värillä
class Coloring:
    def __init__(self,n):
        # TODO

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

    def check(self):
        # TODO

if __name__ == "__main__":
    c = Coloring(4)
    c.add_edge(1,2)
    c.add_edge(2,3)
    c.add_edge(3,4)
    c.add_edge(1,4)
    print(c.check()) # True
    c.add_edge(2,4)
    print(c.check()) # False
Java

Toteuta tiedostoon Coloring.java luokka Coloring, jossa on seuraavat metodit:
  • konstruktori, jolle annetaan solmujen määrä
  • addEdge lisää kaaren kahden solmun välille
  • check tarkastaa, voiko verkon värittää kahdella värillä
public class Coloring {
    public Coloring(int n) {
        // TODO
    }

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

    public boolean check() {
        // TODO
    }

    public static void main(String[] args) {
        Coloring c = new Coloring(4);
        c.addEdge(1,2);
        c.addEdge(2,3);
        c.addEdge(3,4);
        c.addEdge(1,4);
        System.out.println(c.check()); // true
        c.addEdge(2,4);
        System.out.println(c.check()); // false
    }
}