#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
vector<vii> g;
vii ed;
string a = "";
vi v;
vi UFDS;
int pt(int n){
if(UFDS[n]==n)
return n;
else
return UFDS[n] = pt(UFDS[n]);
}
int mrg(int l, int r){
return UFDS[pt(l)] = pt(r);
}
bool dfs_cycle(int n, int p){
if(v[n])
return 1;
v[n] = 1;
bool c = 0;
for(int x=0; x<g[n].size(); x++){
if(g[n][x].second!=p){
if(dfs_cycle(g[n][x].first, g[n][x].second)){
mrg(g[n][x].first, n);
a[g[n][x].second] = 'B';
c = 1;
}
}
}
return c;
}
bool dfs_path(int n, int d){
if(v[n])
return 0;
if(n==d){
return 1;
}
v[n] = 1;
bool r = 0;
for(int x=0; x<g[n].size(); x++){
if(!v[g[n][x].first]){
//not visited yet
if(dfs_path(g[n][x].first, d)){
//reachable
if(a[g[n][x].second]=='0'){
if(ed[g[n][x].second].first==n){
//from first to second
a[g[n][x].second] = 'R';
} else {
a[g[n][x].second] = 'L';
}
}
r=1;
}
}
}
v[n] = 0;
return r;
}
int main(){
int N, M, P; cin>>N>>M;
a = string(M, '0');
int A, B;
g.assign(N+1, vii());
for(int m=0; m<M; m++){
cin>>A>>B;
g[A].push_back({B, m});
g[B].push_back({A, m});
ed.push_back({A, B});
}
UFDS.assign(N+1, 0);
for(int n=0; n<=N; n++)
UFDS[n] = n;
v.assign(N+1, 0);
for(int n=1; n<=N; n++){
// v.assign(N+1, 0);
if(!v[n]){
dfs_cycle(n, -1);
}
}
cin>>P;
// cout << a << endl;
for(int p=0; p<P; p++){
cin>>A>>B;
//find path from A to B, changing edges on the way
v.assign(N+1, 0);
dfs_path(A, B);
}
for(int x=0; x<M; x++){
if(a[x]=='0')
a[x] = 'B';
}
cout << a << endl;
return 0;
}
Compilation message
oneway.cpp: In function 'bool dfs_cycle(int, int)':
oneway.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int x=0; x<g[n].size(); x++){
~^~~~~~~~~~~~
oneway.cpp: In function 'bool dfs_path(int, int)':
oneway.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int x=0; x<g[n].size(); x++){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
