Dla każdej krawędzi należy stwierdzić, czy musi być ona skierowana w konkretną stronę, czy też istnieją poprawne skierowania, w których jest ona skierowana przeciwnie.

Mosty i krawędziowo dwuspójne składowe

Mostem nazywamy krawędź, której usunięcie z grafu zwiększa liczbę spójnych składowych. Naturalne jest podzielenie grafu na składowe połączone mostami. Formalnie takie składowe nazywamy krawędziowo dwuspójnymi. W grafie składowych każdą składową zwijamy do jednego wierzchołka, a wszystkie krawędzie są mostami. Taki graf musi być drzewem.

Każda ścieżka z $a_{i}$ do $b_{i}$ będzie musiała przechodzić przez pewien zbiór mostów, które tworzą ścieżkę w grafie składowych. Tak więc dla tych krawędzi skierowanie jest wymuszone.

Ponadto, w każdej składowej możemy tak skierować krawędzie, aby składowa stała się silnie spójna. Wystarczy uruchomić na tej składowej algorytm DFS i każdą krawędź drzewową skierować w dół, a każdą krawędź powrotną skierować w górę. Zatem będziemy mogli przejść pomiędzy dowolnymi wierzchołkami ze składowej, więc rzeczywiście przy rozważaniu par $(a_{i}, b_{i})$ wystarczy kontrolować skierowanie mostów.

Co więcej, jeśli w skierowaniu składowej zamienimy kierunki wszystkich krawędzi, to nadal dostaniemy silnie spójną składową. Wynika z tego, że w obrębie składowej żadna krawędź nie będzie miała narzuconego kierunku.

Zatem narzucony kierunek będą miały jedynie mosty, przez które przechodzi jakaś ścieżka z $a_{i}$ do $b_{i}$ .

Podzadanie 1

Możemy rozważać każdą krawędź $e$ osobno. Najpierw usuwamy ją z grafu i przeszukujemy graf zaczynając z jej jednego końca. Jeśli dojdziemy w ten sposób do drugiego końca, to krawędź była w składowej, więc możemy ją pominąć.

W przeciwnym wypadku była mostem i przeszukujemy graf z jej drugiego końca. Mamy zatem zaznaczone wierzchołki dwóch części grafu $A$ i $B$ , które były połączone mostem. Analizujemy teraz wszystkie pary $(a_{i}, b_{i})$ i jeżeli $a_{i} \in A$ , a $b_{i} \in B$ (albo na odwrót), to para taka wyznacza skierowanie krawędzi $e$ .

Złożoność czasowa to $O (m (m + p))$ :

const int N = 110000;
int n,m,p;
vector<pair<int,int>> adj[N];
int ea[N],eb[N];
int pa[N],pb[N];
char ans[N];
int vis[N];

void dfs(int v, int bad, int col) {
  vis[v] = col;
  for (auto p : adj[v]) {
    if (vis[p.first]) continue;
    if (p.second == bad) continue;
    dfs(p.first, bad, col);
  }
}

int main() {
  scanf("%d%d",&n,&m);
  REP(i,m) {
    int a,b; scanf("%d%d",&a,&b);
    --a; --b;
    ea[i] = a; eb[i] = b;
    adj[a].emplace_back(b, i);
    adj[b].emplace_back(a, i);
  }
  scanf("%d",&p);
  REP(i,p) {
    scanf("%d%d",&pa[i],&pb[i]);
    --pa[i]; --pb[i];
  }

  REP(i,m) {
    REP(j,n) vis[j] = 0;
    dfs(ea[i], i, 1);
    if (vis[eb[i]] == 1) {
      ans[i] = 'B';
      continue;
    }
    dfs(eb[i], i, 2);

    int mustl=0, mustr=0;

    REP(j,p) {
      if (vis[pa[j]] == 1 && vis[pb[j]] == 2) mustr = 1;
      else if (vis[pa[j]] == 2 && vis[pb[j]] == 1) mustl = 1;
    }
    assert(!(mustl && mustr));
    if (mustl) ans[i] = 'L';
    else if (mustr) ans[i] = 'R';
    else ans[i] = 'B';
  }

  puts(ans);
}

Rozwiązanie ogólne

Istnieją standardowe algorytmy szukania mostów, działające w czasie $O (m + n)$ .

W każdym wierzchołku w grafie składowych zapamiętujemy ile mamy w nim początków $a_{i}$ , a ile końców $b_{i}$ . Teraz ukorzeniamy drzewo składowych i przechodzimy je DFS-em. W wierzchołku $v$ , po przejściu całego poddrzewa zaczepionego w $v$ , znamy sumaryczną liczbę $A$ początków i sumaryczną liczbę $B$ końców, które są w tym poddrzewie.

Jeśli $A > B$ , to krawędź $e$ z $v$ do ojca musi być skierowana w górę, bo co najmniej jeden początek z poddrzewa nie będzie sparowany z końcem z poddrzewa (więc jego ścieżka musi przechodzić przez krawędź $e$ ). Analogicznie dla $A < B$ krawędź $e$ musi być skierowana w dół.

W przypadku $A = B$ początki i końce z poddrzewa muszą być sparowane między sobą (bo w treści zadania mamy założenie, że istnieje poprawne skierowanie krawędzi), zatem krawędź $e$ może być skierowana dowolnie.

Poniżej implementacja tego pomysłu, działająca w czasie $O (m + n + p)$ :

const int N = 110000;
int n,m,p;
vector<pair<int,int>> adj[N];
int ea[N],eb[N];
int pa[N],pb[N];
char ans[N];
int low[N],tin[N],T;
int bridge[N],comp[N],C,value[N],vis[N];
vector<pair<int,int>> adj2[N];

void dfs(int v, int par) {
  tin[v] = low[v] = T++;
  for (auto [u, e] : adj[v]) if (u != par) {
    if (tin[u] == -1) {
      dfs(u, v);
      if (low[u] >= tin[u]) {
        bridge[e] = 1;
      }
      low[v] = min(low[v], low[u]);
    } else {
      low[v] = min(low[v], tin[u]);
    }
  }
}

void dfs2(int v) {
  comp[v] = C;
  for (auto [u, e] : adj[v]) {
    if (!bridge[e] && comp[u] == -1) {
      dfs2(u);
    }
  }
}

int dfs3(int v, int par) {
  vis[v] = 1;
  int my_val = value[v];
  for (auto [u, edge] : adj2[v]) if (u != par) {
    int val = dfs3(u, v);
    int e = edge >= 0 ? edge : ~edge;
    if (val != 0) {
      ans[e] = (val > 0) == (edge < 0) ? 'R' : 'L';
    } else {
      ans[e] = 'B';
    }
    my_val += val;
  }
  return my_val;
}

int main() {
  scanf("%d%d",&n,&m);
  REP(i,m) {
    int a,b; scanf("%d%d",&a,&b);
    --a; --b;
    ea[i] = a; eb[i] = b;
    adj[a].emplace_back(b, i);
    adj[b].emplace_back(a, i);
  }
  scanf("%d",&p);
  REP(i,p) {
    scanf("%d%d",&pa[i],&pb[i]);
    --pa[i]; --pb[i];
  }

  REP(i,n) tin[i] = -1;
  REP(i,n) if (tin[i] == -1) {
    dfs(i, -1);
  }

  REP(i,n) comp[i] = -1;
  REP(i,n) if (comp[i] == -1) {
    dfs2(i);
    ++C;
  }

  REP(i,n) for (auto [u, e] : adj[i]) {
    if (comp[i] < comp[u]) {
      assert(bridge[e]);
      int edge = ea[e] == i ? e : ~e;
      adj2[comp[i]].emplace_back(comp[u], edge);
      adj2[comp[u]].emplace_back(comp[i], ~edge);
    }
  }

  REP(i,p) {
    value[comp[pa[i]]]++;
    value[comp[pb[i]]]--;
  }

  REP(i,m) ans[i] = 'B';

  REP(i,C) if (!vis[i]) {
    dfs3(i, -1);
  }

  puts(ans);
}