#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,m;
pair<int,int> edge[MAXN];
vector<pair<int,int> > adj[MAXN];
int par[MAXN];
int dep[MAXN];
int low[MAXN];
bool vis[MAXN];
bool bri[MAXN];
void dfs(int x,int d){
vis[x]=1;
dep[x]=low[x]=d;
for(int i=0;i<(int)adj[x].size();i++){
int y=adj[x][i].first;
if(!vis[y]){ //not yet visited
par[y]=x;
dfs(y,d+1);
if(low[y]>dep[x]&&adj[x][i].second>0)bri[adj[x][i].second]=1;
low[x]=min(low[x],low[y]);
}else if(y!=par[x])low[x]=min(low[x],dep[y]); //visited and is not parent
}
}
int scc[MAXN];
int c=0;
void comp(int x){
scc[x]=c;
for(int i=0;i<(int)adj[x].size();i++){
if(!bri[adj[x][i].second]&&scc[adj[x][i].first]==-1)comp(adj[x][i].first);
}
}
vector<pair<int,int> > adj2[MAXN];
pair<int,int> q[MAXN];
vector<pair<int,int> > r;
int pa[MAXN][19];int idx[MAXN];
int ldep[MAXN];
void dfs2(int x){
for(int i=0;i<(int)(adj2[x].size());i++){
int y=adj2[x][i].first;
if(pa[y][0]==-1){
pa[y][0]=x;idx[y]=adj2[x][i].second;
ldep[y]=ldep[x]+1;
dfs2(y);
}
}
}
int lca(int x,int y){
if(x==y)return x;
if(ldep[x]<ldep[y])swap(x,y);
for(int i=19;i>=0;i--){
if(pa[x][i]!=-1&&ldep[pa[x][i]]>=ldep[y])x=pa[x][i];
}
if(x==y)return x;
for(int i=19;i>=0;i--){
if(pa[x][i]!=pa[y][i]){x=pa[x][i];y=pa[y][i];}
}
return pa[x][0];
}
int ans[MAXN]; //0 B, 1 R, -1 L
void dir(int x,int y,int d){
if(x==y)return;
if(ans[idx[x]]!=0)return;
int a=edge[idx[x]].first,b=edge[idx[x]].second;
if(d==1){
if(x==scc[a])ans[idx[x]]=1;
else ans[idx[x]]=-1;
}else{
if(x==scc[b])ans[idx[x]]=1;
else ans[idx[x]]=-1;
}
}
int main(){
scanf("%d%d",&n,&m);
memset(par,-1,sizeof(par));
int a,b;
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);a--;b--;edge[i]=make_pair(a,b);
adj[a].push_back(make_pair(b,i));adj[b].push_back(make_pair(a,i));
}
for(int i=0;i<n;i++)if(!vis[i])dfs(i,0);
memset(scc,-1,sizeof(scc));
for(int i=0;i<n;i++)if(scc[i]==-1)comp(i),c++;
for(int i=0;i<m;i++){
a=edge[i].first,b=edge[i].second;
if(scc[a]==scc[b])continue;
adj2[scc[a]].push_back(make_pair(scc[b],i));adj2[scc[b]].push_back(make_pair(scc[a],i));
}
//for(int i=0;i<c;i++){for(int j=0;j<(int)adj2[i].size();j++)printf("%d ",adj2[i][j].first);printf("\n");}
memset(pa,-1,sizeof(pa));for(int i=0;i<n;i++)if(pa[i][0]==-1)dfs2(i);
for(int i=1;i<19;i++)for(int j=0;j<n;j++)if(pa[j][i-1]!=-1)pa[j][i]=pa[pa[j][i-1]][i-1];
int p;
scanf("%d",&p);
for(int i=0;i<p;i++){
scanf("%d%d",&q[i].first,&q[i].second);q[i].first--;q[i].second--;
if(scc[q[i].first]==scc[q[i].second])continue;
r.push_back(make_pair(lca(scc[q[i].first],scc[q[i].second]),i));
}
sort(r.begin(),r.end());
for(int i=0;i<(int)r.size();i++){
a=q[r[i].second].first,b=q[r[i].second].second;
//printf("%d->%d->%d\n",a,r[i].first,b);
dir(scc[a],r[i].first,1);
dir(scc[b],r[i].first,-1);
}
for(int i=0;i<m;i++){
if(ans[i]==0)printf("B");
else if(ans[i]==1)printf("R");
else printf("L");
}
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
oneway.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);a--;b--;edge[i]=make_pair(a,b);
~~~~~^~~~~~~~~~~~~~
oneway.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&p);
~~~~~^~~~~~~~~
oneway.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&q[i].first,&q[i].second);q[i].first--;q[i].second--;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
13312 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
13312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
13312 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
13312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
13312 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
13312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
