Joker

Dany jest graf nieskierowany o $N$ wierzchołkach i $M$ krawędziach. Mamy odpowiedzieć na $Q$ zapytań, każde postaci $(l,r)$, co oznacza pytanie „czy w grafie istnieje cykl o długości nieparzystej, jeśli usuniemy z niego krawędzie o numerach z przedziału $[l,r]$”.

Rozwiązanie brutalne

W podzadaniu 1 można rozważyć każde zapytanie oddzielnie i uruchomić algorytm DFS, żeby sprawdzić, czy istnieje cykl długości nieparzystej. Korzystamy tutaj z faktu, że jeśli istnieje cykl długości nieparzystej, to jakiś cykl długości nieparzystej zostanie znaleziony przez DFS (nie musi to być prawdą dla cykli długości parzystej). Złożoność czasowa to $O(Q(N+M))$.

Brak cyklu o długości nieparzystej jest równoważny temu, że graf jest dwudzielny. Oraz że istnieje dwukolorowanie tego grafu (czyli kolorowanie wierzchołków na dwa kolory tak, by wierzchołki połączone krawędzią miały różne kolory).

Rozwiązanie szybsze

Podzadanie 3 można zrobić na dwa sposoby. Możemy posortować wszystkie zapytania malejąco po końcach r[i]. Następnie będziemy dodawać do grafu krawędzie od końca i za każdym razem, gdy natrafimy na zapytanie, patrzymy czy graf jest dwudzielny.

To wymaga posiadania struktury danych, która umożliwia dodawanie krawędzi do grafu i sprawdzanie dwudzielności.

Możemy to zrobić przez rozszerzenie struktury dla zbiorów rozłącznych (DSU). Dla każdego wierzchołka v trzymamy jego wartość fu[v] (która jeśli jest nieujemna, oznacza numer rodzica, a jeśli jest ujemna, to oznacza, że v jest korzeniem drzewa rozmiaru -fu[v]). Oprócz tego, jeśli v nie jest korzeniem, to trzymamy zmienną col[v], która jest 0, jeśli kolor v jest taki sam, jak jego rodzica, a 1 jeśli inny (kolory w dwukolorowaniu dla spójnej składowej są wyznaczone jednoznacznie, jak ustalimy kolor dowolnego wierzchołka).

struct dsu_t {
  int n;
  vector<int> fu, col;
  int bad;

  dsu_t(int _n) : n(_n), bad(0) {
    fu.assign(n, -1);
    col.resize(n);
  }

  int find(int x, int& c) const {
    while (fu[x] >= 0) { c ^= col[x]; x = fu[x]; }
    return x;
  }

  bool insert_edge(int a, int b) {
    int ca = 0, cb = 0;
    a = find(a, ca);
    b = find(b, cb);
    if (a == b) {
      if (ca == cb) { bad++; }
      return false;
    } else {
      if (-fu[a] < -fu[b]) { swap(a, b); swap(ca, cb); }
      fu[a] += fu[b];
      fu[b] = a;
      col[b] = ca ^ 1 ^ cb;
      return true;
    }
  }

  bool is_bipartite() const { return bad == 0; }
};

Jeśli dodajemy krawędź, to dla każdego wierzchołka wyznaczamy korzeń jego poddrzewa oraz zmienną oznaczającą, jaki mają kolor względem korzenia (to można zrobić przejściem po ścieżce do korzenia).

Jeśli wierzchołki są w tej samej składowej, to sprawdzamy ich kolory. Jeśli są takie same, to ustawiamy, że graf już nie jest dwudzielny.

Jeśli są w różnych składowych, to podłączamy metodą „mniejszy do większego”, a następnie uaktualniamy wagę nowej krawędzi. Metoda daje nam gwarancję, że wysokości drzew będą $O(\log n)$.

Reszta kodu jest następująca:

int main() {
  scanf("%d%d%d",&n,&m,&q);
  REP(i,m) {
    int a,b; scanf("%d%d",&a,&b); --a;--b;
    A[i] = a;
    B[i] = b;
  }

  for (int i=0; i<q; ++i) {
    scanf("%d%d",&L[i],&R[i]); --L[i];
  }
  iota(idx, idx+q, 0);
  sort(idx, idx+q, [](int i, int j) { return R[i] > R[j]; });

  dsu_t graph(n);

  int E = m;
  for (int i=0; i<q; ++i) {
    int id = idx[i];
    while (E > R[id]) {
      --E;
      graph.insert_edge(A[E], B[E]);
    }
    ans[id] = ! graph.is_bipartite();
  }

  for (int i=0; i<q; ++i) {
    printf("%s\n", ans[i] ? "YES" : "NO");
  }
}

Złożoność to $O(q\log q + m\log n)$.

Inna metoda to zauważenie, że dla ustalonego l możemy znaleźć minimalne r = last[l], że zapytanie $[l,r)$ jest ok, ale zapytanie $[l,r-1)$ już nie. Więc możemy zrobić wyszukiwanie binarne po tej wartości (a w środku normalne dwukolorowanie).

Teraz odpowiedź na zapytanie to sprawdzenie czy r \geq last[l].

Rozwiązanie alternatywne

Można to zadanie zrobić algorytmem Mo. Będziemy teraz jednak potrzebować zarówno dodawania jak i usuwania krawędzi. Usuwanie dowolnych krawędzi jest trudne, ale w miarę łatwo można zmodyfikować strukturę DSU, aby usuwała ostatnio dodaną krawędź (czyli z operacją „cofnięcia”).

struct dsu_t {
  int n;
  vector<int> fu, col;
  int bad;

  struct oper_t {
    int a, b, size, ba;
    oper_t(int a, int b, int size, int ba) : a(a), b(b), size(size), ba(ba) { }
  };
  vector<oper_t> opers;
  vector<int> saves;


  dsu_t(int _n) : n(_n), bad(0) {
    fu.assign(n, -1);
    col.resize(n);
  }

  int find(int x, int& c) const {
    while (fu[x] >= 0) { c ^= col[x]; x = fu[x]; }
    return x;
  }

  bool insert_edge(int a, int b) {
    int ca = 0, cb = 0;
    a = find(a, ca);
    b = find(b, cb);
    if (a == b) {
      if (ca == cb) { bad++; }
      opers.emplace_back(a, b, 0, ca == cb);
      return false;
    } else {
      if (-fu[a] < -fu[b]) { swap(a, b); swap(ca, cb); }
      opers.emplace_back(a, b, fu[b], 0);
      fu[a] += fu[b];
      fu[b] = a;
      col[b] = ca ^ 1 ^ cb;
      return true;
    }
  }

  bool is_bipartite() const { return bad == 0; }

  void rollback() {
    oper_t op = opers.back();
    opers.pop_back();

    if (op.size < 0) {
      fu[op.b] = op.size;
      fu[op.a] -= op.size;
    } else {
      bad -= op.ba;
    }
  }

  void save() {
    saves.push_back(opers.size());
  }

  void restore() {
    while (opers.size() > saves.back()) { rollback(); }
    saves.pop_back();
  }
};

Po prostu mamy operacje trzymamy na stosie wykonanych operacji i cofamy to co zrobiliśmy. W związku z tym nie mamy tutaj kompresji ścieżek.

Wygodnie jest również mieć operację, która zapisuje moment w czasie (save), a potem operację restore, która cofa wszystkie dodane krawędzie do momentu z zapisu.

Potrzebujemy zatem wariant algorytmu Mo, w którym prawy wskaźnik będzie dodawał krawędzie, a lewy wskaźnik będzie dodawał, a potem je cofał.

int main() {
  scanf("%d%d%d",&n,&m,&q);
  REP(i,m) {
    scanf("%d%d",&a[i],&b[i]); --a[i]; --b[i];
  }

  for (int i=0; i<q; ++i) {
    scanf("%d%d",&L[i],&R[i]); --L[i];
  }

  dsu_t graph(n);


  /* Mo */
  const int B = m/sqrt(q), QB = m/B+1;
  vector<int> qu[QB];
  for (int i=0; i<q; ++i) {
    assert(L[i]/B < QB);
    qu[L[i]/B].push_back(i);
  }

  auto insert = [&](int e) { graph.insert_edge(a[e], b[e]); };

  REP(i,QB) {
    int beg = i*B;
    int end = min(m, (i+1)*B);
    sort(qu[i].begin(), qu[i].end(), [](int i, int j) { return R[i] > R[j]; });

    int E = m;
    graph.save();
    for (int idx : qu[i]) {
      assert(beg <= L[idx] && L[idx] < end);
      while (E > R[idx]) { insert(--E); }
      graph.save();
      FOR(j,beg,L[idx]) { insert(j); }
      ans[idx] = ! graph.is_bipartite();
      graph.restore();
    }
    graph.restore();

    FOR(j,beg,end) { insert(j); }
  }


  for (int i=0; i<q; ++i) {
    printf("%s\n", ans[i] ? "YES" : "NO");
  }
}