#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 10;
int n, m, p;
int from[N], to[N];
vector<pair<int, bool>> ad[N];
int a[N], b[N];
namespace BCC {
vector<int> ad[N];
int low[N], num[N], it;
stack<int> st;
int bcc[N], cc;
void dfs(int u, int p = -1) {
low[u] = num[u] = ++it;
st.push(u);
bool pass = false;
for (const auto& v : ad[u]) {
if (bcc[v] || v == p && !pass) {
pass = true;
continue;
}
if (!low[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], num[v]);
}
if (low[u] == num[u]) {
bcc[u] = ++cc;
while (st.top() != u) {
bcc[st.top()] = cc;
st.pop();
} st.pop();
}
}
}
int st[N], ed[N], it;
int par[N], d[N];
bool mk[N], vst[N];
void dfs(int u, int p = - 1) {
st[u] = ++it;
for (const auto& [v, way] : ad[u]) {
if (v == p) continue;
par[v] = u;
d[v] = d[u] + 1;
mk[v] = way;
dfs(v, u);
}
ed[u] = it;
}
bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int id[N];
int root(int u) { return !id[u] ? u : id[u] = root(id[u]); }
void add(int u, int v) {
u = root(u); v = root(v);
if (u == v) return;
if (d[u] > d[v]) swap(u, v);
id[v] = u;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) cin >> from[i] >> to[i];
cin >> p;
for (int i = 1; i <= p; ++i) cin >> a[i] >> b[i];
for (int i = 1; i <= m; ++i) {
int u = from[i], v = to[i];
BCC::ad[u].push_back(v);
BCC::ad[v].push_back(u);
}
BCC::dfs(1);
for (int i = 1; i <= m; ++i) {
int u = BCC::bcc[from[i]], v = BCC::bcc[to[i]];
if (u == v) continue;
ad[u].push_back({v, true});
ad[v].push_back({u, false});
}
dfs(par[1] = 1);
for (int i = 1; i <= p; ++i) {
int u = BCC::bcc[a[i]], v = BCC::bcc[b[i]];
if (u == v) continue;
u = root(u); v = root(v);
for (int t = 1; t >= 0; --t) {
vector<int> vt;
while (!anc(u, v)) {
vt.push_back(u);
u = par[root(u)];
}
for (const auto& x : vt) {
add(x, vt.end()[-1]);
mk[x] ^= t;
vst[x] = true;
}
swap(u, v);
}
}
for (int i = 1; i <= m; ++i) {
int u = from[i], v = to[i];
int x = BCC::bcc[u], y = BCC::bcc[v];
if (x == y) cout << 'B';
else if (anc(x, y)) cout << (!vst[y] ? 'B' : mk[y] ? 'R' : 'L');
else cout << (!vst[x] ? 'B' : mk[x] ? 'R' : 'L');
}
cout << "\n";
}
Compilation message
oneway.cpp: In function 'void BCC::dfs(int, int)':
oneway.cpp:21:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
21 | if (bcc[v] || v == p && !pass) {
| ~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
