#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
vector<array<int, 2>> adj[N];
vector<array<int, 2>> adj2[N];
bool isBridge[N];
int up[N];
int in[N];
int out[N];
int timer;
int n, m;
int group[N];
array<int, 2> par[N];
int goNext[N];
array<int, 2> direction[N];
map<array<int, 2>, int> groupEdgeToNode;
void bridges(int node, array<int, 2> par) {
in[node] = timer++;
up[node] = in[node];
for (auto next : adj[node]) {
if (next[0] == par[0]) continue;
if (in[next[0]]) {
up[node] = min(up[node], in[next[0]]);
} else {
bridges(next[0], {node, next[1]});
up[node] = min(up[node], up[next[0]]);
}
}
if (node != 1 && up[node] == in[node]) {
isBridge[par[1]] = true;
}
}
void clean() {
for (int i = 0; i <= n; i++) {
up[i] = 0;
in[i] = 0;
}
for (int i = 0; i <= m; i++) {
isBridge[i] = false;
}
timer = 1;
}
void assignGroup(int node, int cgroup) {
group[node] = cgroup;
for (auto next : adj[node]) {
if (!group[next[0]] && !isBridge[next[1]]) {
assignGroup(next[0], cgroup);
}
}
}
void dfs(int node, array<int, 2> p) {
in[node] = ++timer;
par[node] = p;
for (auto next : adj2[node]) {
if (next == p) continue;
dfs(next[0], {node, next[1]});
}
out[node] = timer;
}
void query(int node, int other, bool first) {
if (goNext[node] != node) {
query(goNext[node], other, first);
goNext[node] = goNext[goNext[node]];
} else {
if (in[node] <= in[other] && out[other] <= out[node]) {
} else {
if (first) {
direction[par[node][1]] = {groupEdgeToNode[{node, par[node][0]}], groupEdgeToNode[{par[node][0], node}]};
} else {
direction[par[node][1]] = {groupEdgeToNode[{par[node][0], node}], groupEdgeToNode[{node, par[node][0]}]};
}
query(goNext[par[node][0]], other, first);
goNext[node] = goNext[par[node][0]];
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
vector<array<int, 2>> edgeNodes(m);
for (int i = 0; i< m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back({b, i});
adj[b].push_back({a, i});
edgeNodes[i] = {a, b};
}
timer = 1;
bridges(1, {-1, -1});
string res(m, 'B');
int cgroup = 1;
for (int i = 1; i <= n; i++) {
if(!group[i]) assignGroup(i, cgroup++);
}
for (int i = 1; i <= n; i++) {
for (auto next : adj[i]) {
if (group[i] != group[next[0]]) {
groupEdgeToNode[{group[i], group[next[0]]}] = i;
adj2[group[i]].push_back({group[next[0]], next[1]});
}
}
}
clean();
dfs(1, {-1, -1});
for (int i = 0; i <N; i++) goNext[i] = i;
int p;
cin >> p;
for (int p1 = 0; p1 < p; p1++) {
int x, y;
cin >> x >> y;
if (group[x] != group[y]) {
query(group[x], group[y], true);
query(group[y], group[x], false);
}
}
for (int i = 0; i < m; i++) {
array<int, 2> compareArray = {0, 0};
if (direction[i] != compareArray) {
if (direction[i] == edgeNodes[i]) res[i] = 'R';
else res[i] = 'L';
}
}
cout << res << "\n";
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
