LOJ #2480. 「CEOI2017」One-Way Streets

题目链接：​​传送门​​

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
struct Graph {
  class node {
  public:
    node(){};
    ~node(){};
    int next, to, id;
  }e[A];
  int head[A], num = 1;
  template<typename AD>
  void add(AD fr, AD to, AD id) {
    e[++num].next = head[fr];
    e[num].to = to;
    e[num].id = id;
    head[fr] = num;
  }
}g1, g2;
int n, m, a[A], b[A]; bool vis[A];
int dfn[A], low[A], sta[A], cnt, top, kn, bl[A];
template<typename T>
void tarjan(T fr, T fa) {
  dfn[fr] = low[fr] = ++cnt, vis[fr] = 1, sta[++top] = fr;
  for (int i = g1.head[fr]; i; i = g1.e[i].next) {
    if ((i ^ 1) == fa) continue;
    int ca = g1.e[i].to;
    if (!dfn[ca]) tarjan(ca, i), low[fr] = min(low[fr], low[ca]);
    else if (vis[ca]) low[fr] = min(low[fr], dfn[ca]);
  }
  if (low[fr] == dfn[fr]) {
    int p; kn++;
    do {
      p = sta[top--];
      vis[p] = 0;
      bl[p] = kn;
    }while (p != fr);
  }
}
int c1[A], c2[A], ans[A];
namespace Cut {
  int dep[A], dfn[A], top[A], siz[A], son[A], cnt, fa[A];
  template<typename P>
  void prepare(P fr) {
    siz[fr] = 1;
    for (int i = g2.head[fr]; i; i = g2.e[i].next) {
      int ca = g2.e[i].to;
      if (ca == fa[fr]) continue;
      fa[ca] = fr; dep[ca] = dep[fr] + 1;
      prepare(ca); siz[fr] += siz[ca];
      if (siz[ca] > siz[son[fr]]) son[fr] = ca;
    }
  }
  template<typename D>
  void dfs(D fr, D tp) {
    dfn[fr] = ++cnt; top[fr] = tp;
    if (son[fr]) dfs(son[fr], tp);
    for (int i = g2.head[fr]; i; i = g2.e[i].next) {
      int ca = g2.e[i].to;
      if (ca == son[fr] or ca == fa[fr]) continue;
      dfs(ca, ca);
    }
  }
  template<typename L>
  int lca(L x, L y) {
    while (top[x] != top[y]) {
      if (dep[top[x]] < dep[top[y]]) swap(x, y);
      x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
  }
}
template<typename D>
void dfs(D fr) {
  vis[fr] = 1; bool ok = 1;
  for (int i = g2.head[fr]; i; i = g2.e[i].next) {
    int ca = g2.e[i].to;
    if (ca == Cut::fa[fr]) continue;
    if (!vis[ca]) dfs(ca), ok = 0;
    if (c1[ca] > 0) ans[g2.e[i].id] = i % 2 ? 1 : 2;
    if (c2[ca] > 0) ans[g2.e[i].id] = i % 2 ? 2 : 1;
    if (!ok) c1[fr] += c1[ca], c2[fr] += c2[ca];
  }
}

int main(int argc, char const *argv[]) {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &a[i], &b[i]);
    g1.add(a[i], b[i], i); g1.add(b[i], a[i], i);
  }
  for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i);
  for (int i = 1; i <= m; i++) if (bl[a[i]] != bl[b[i]])
    g2.add(bl[a[i]], bl[b[i]], i), g2.add(bl[b[i]], bl[a[i]], i);
  Cut::prepare(1); Cut::dfs(1, 1);
  int q, x, y; cin >> q;
  while (q--) {
    scanf("%d%d", &x, &y);
    x = bl[x], y = bl[y];
    if (x == y) continue;
    int Lca = Cut::lca(x, y);
    c1[x]++; c2[y]++; c1[Lca]--; c2[Lca]--;
  }
  memset(vis, 0, sizeof vis);
  for (int i = 1; i <= kn; i++) if (!vis[i]) dfs(i);
  for (int i = 1; i <= m; i++) {
    if (ans[i] == 0) putchar('B');
    if (ans[i] == 1) putchar('R');
    if (ans[i] == 2) putchar('L');
  }
  return 0;
}