#include <bits/stdc++.h>
using namespace std;
#define int int64_t
vector<int> pre;
vector<int> low;
vector<vector<int>> graph;
map<pair<int,int>,int> edges;
vector<pair<int,int>> indedge;
vector<bool> bridges;
int tim;
void dfs1(int v, int p=-1){
pre[v]=tim++;
low[v]=pre[v];
for(auto u:graph[v]){
if(u==p)continue;
if(pre[u]==-1){
dfs1(u,v);
low[v]=min(low[v],low[u]);
if(low[u]>pre[v]){
int ind=edges[{v,u}];
bridges[ind]=true;
}
}else{
low[v]=min(low[u], low[v]);
}
}
}
string s;
vector<bool> visited;
bool dfs2(int v, int t){
if(visited[v]) return false;
visited[v]=true;
if(v==t)return true;
for(auto u:graph[v]){
if(dfs2(u,t)){
int in=edges[{v,u}];
if(bridges[in]){
if(v==indedge[in].first){
s[in]='R';
}else{
s[in]='L';
}
}
return true;
}
}
return false;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
tim=0;
int n,m;
cin>>n>>m;
pre.resize(n,-1);
low.resize(n,-1);
bridges.resize(m);
graph.resize(n);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;
b--;
graph[a].push_back(b);
graph[b].push_back(a);
indedge.push_back({a,b});
edges[{a,b}]=i;
edges[{b,a}]=i;
}
dfs1(0);
s.resize(m,'B');
int p;
cin>>p;
for(int i=0;i<p;i++){
int x,y;
cin>>x>>y;
x--;
y--;
visited.assign(n,false);
bool b=dfs2(x,y);
}
cout<<s<<"\n";
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:89:14: warning: unused variable 'b' [-Wunused-variable]
89 | bool b=dfs2(x,y);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
