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.
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$.
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); }
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); }