#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
using namespace std;
int n, m, low[MAXN], tin[MAXN], tout[MAXN], timer, col[MAXN], logg;
vector<int> g[MAXN], gg[MAXN];
vector<pii> bridge, grane;
vector<pair<int, pii> >svi;
bool bio[MAXN];
map<pii, bool> b;
map<pii, int> dir, cnt;
int up[MAXN][25];
void dfs(int u, int p)
{
bio[u]=true;
tin[u]=low[u]=timer++;
for (auto v:g[u])
{
if (v==p) continue;
if (bio[v])
low[u]=min(low[u], tin[v]);
else
{
dfs(v, u);
low[u]=min(low[u], low[v]);
if (low[v]>tin[u] && cnt[{u, v}]==1) { cout<<u<<" bridge "<<v<<endl; bridge.pb({u, v}); b[{u, v}]=b[{v, u}]=true; }
}
}
}
void dfs2(int u, int c)
{
bio[u]=true;
col[u]=c;
for (auto v:g[u])
{
if (!bio[v] && !b[{u, v}]) dfs2(v, c);
}
}
void dfs3(int u, int p)
{
///cout<<u<<" dfs3 "<<timer+1<<endl;
bio[u]=true;
tin[u]=++timer;
up[u][0]=p;
for (int i=1; i<=logg; i++) up[u][i]=up[up[u][i-1]][i-1];
for (auto v:gg[u])
if (!bio[v])
dfs3(v, u);
tout[u]=++timer;
}
bool isanc(int u, int v) ///is u ancestor of v?
{
return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}
int lca(int u, int v)
{
///cout<<tin[u]<<" "<<tout[u]<<" "<<tin[v]<<" "<<tout[v]<<endl;
if (isanc(u, v)) return u;
if (isanc(v, u)) return v;
for (int i=logg; i>=0; i--)
{
if (!isanc(up[u][i], v)) u=up[u][i];
}
return up[u][0];
}
int main() {
cin>>n>>m;
for (int i=0; i<m; i++)
{
int u, v; cin>>u>>v;
grane.pb({u, v}); cnt[{u, v}]++; cnt[{v, u}]++;
g[u].pb(v);
g[v].pb(u);
}
for (int i=1; i<=n; i++)
{
if (!bio[i])
dfs(i, -1);
}
for (int i=1; i<=n; i++) bio[i]=false;
int cc=1;
for (int i=1; i<=n; i++)
{
if (!bio[i]) { dfs2(i, cc); cc++; }
}
//for (int i=1; i<=n; i++) cout<<col[i]<<" ";
//cout<<endl;
for (int i=0; i<bridge.size(); i++)
{
int u=col[bridge[i].xx], v=col[bridge[i].yy];
///cout<<"povezujem "<<u<<" "<<v<<endl;
gg[u].pb(v); gg[v].pb(u);
}
for (int i=1; i<cc; i++) bio[i]=false;
logg=ceil(log2(cc));
timer=0;
for (int i=1; i<cc; i++)
{
if (!bio[i]) dfs3(i, i);
}
int pp; cin>>pp;
while (pp--)
{
int x, y;
cin>>x>>y;
x=col[x];
y=col[y];
if (x==y) continue;
int xy=lca(x, y);
svi.pb({tin[xy], {x, y}});
}
sort(svi.begin(), svi.end());
for (auto par:svi)
{
int x=par.yy.xx; int y=par.yy.yy;
if (x==y) continue;
int xy=lca(x, y);
//cout<<x<<" "<<y<<" "<<xy<<endl;
while (x!=xy)
{
int p=up[x][0];
if (dir[{x, p}]) break;
//cout<<x<<" xp "<<p<<endl;
dir[{x, p}]=1;
dir[{p, x}]=2;
x=p;
}
while (y!=xy)
{
int p=up[y][0];
if (dir[{y, p}]) break;
//cout<<y<<" yp "<<p<<endl;
dir[{y, p}]=2;
dir[{p, y}]=1;
y=p;
}
}
for (int i=0; i<m; i++)
{
int u, v; u=grane[i].xx; v=grane[i].yy;
if (col[u]==col[v]) { cout<<'B'; continue; }
u=col[u]; v=col[v];
//cout<<u<<" uv "<<v<<endl;
if (dir[{u, v}]==1) { cout<<'R'; }
else if (dir[{u, v}]==2) { cout<<'L'; }
else { cout<<'B'; }
}
}
/*
3 5
1 2
2 1
3 4
4 3
2 3
4
1 3
1 2
3 4
1 1
*/
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int i=0; i<bridge.size(); i++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
