#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
const int mxn=1e5+5;
vector<pii>adj[mxn];
vector<int>nw[mxn];
int val[mxn];
int d[mxn];
struct edge{
int v,u;
};
vector<edge>e;
bitset<mxn>vis;
int lv[mxn],low[mxn];
int timer=0;
stack<int>st;
vvi bcc;
vector<int>group(mxn);
vector<bool>bridge(mxn);
void tarjan(int v,int pa,int id=-1){
vis[v]=1;
lv[v]=low[v]=++timer;
st.push(v);
for(auto [u,idx]:adj[v]){
if(idx==id)continue;
if(vis[u]){
chmin(low[v],lv[u]);
}
else{
tarjan(u,v,idx);
chmin(low[v],low[u]);
}
}
if(lv[v]==low[v]){
bridge[id]=1;
bcc.pb({});
while(st.top()!=v){
bcc.back().pb(st.top());
group[st.top()]=sz(bcc)-1;
st.pop();
}
bcc.back().pb(st.top());
group[st.top()]=sz(bcc)-1;
st.pop();
}
}
void dfs2(int v,int pa=0){
d[v]=d[pa]+1;
vis[v]=1;
for(auto u:nw[v]){
if(vis[u])continue;
dfs2(u,v);
val[v]+=val[u];
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
e.pb({a,b});
adj[a].pb({b,i});
adj[b].pb({a,i});
}
tarjan(1,1);
for(int i=1;i<=m;i++){
int a=e[i].v;
int b=e[i].u;
if(bridge[i]){
int x=group[a];
int y=group[b];
nw[x].pb(y);
nw[y].pb(x);
}
}
vector<char>ans(m+1,'B');
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
val[group[a]]++;
val[group[b]]--;
}
vis.reset();
for(int i=0;i<sz(bcc);i++){
if(!vis[i])dfs2(i);
for(auto j:bcc[i])cout<<j<<' ';
cout<<val[i]<<'\n';
}
for(int i=0;i<m;i++){
int x=group[e[i].v];
int y=group[e[i].u];
if(x==y){
cout<<"B";
}
else{
if(d[x]>d[y]){
if(val[x]==0)cout<<"B";
else if(val[x]>0)cout<<"R";
else cout<<"L";
}
else{
if(val[y]==0)cout<<"B";
else if(val[y]<0)cout<<"R";
else cout<<"L";
}
}
}cout<<'\n';
}
/*
input:
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
7 ms |
11564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
7 ms |
11564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
7 ms |
11564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
