#include <bits/stdc++.h>
using namespace std;
struct node{
int depth;
bool vis = false;
int low;
int p;
int up = 0; ///0 - undecided, 1 - up to parent, 2 - down to child
vector<int> adj;
};
node g1[100005];
typedef pair<int,int> ii;
set<ii> bridges;
void dfs(int u){
if(g1[u].vis) return;
g1[u].low = g1[u].depth;
g1[u].vis = true;
for(int i = 0;i < g1[u].adj.size();i++){
int v = g1[u].adj[i];
if(!g1[v].vis){
g1[v].depth = g1[u].depth + 1;
g1[v].p = u;
dfs(v);
g1[u].low = min(g1[v].low,g1[u].low);
if(g1[v].low > g1[u].depth){
bridges.insert(ii(u,v));
bridges.insert(ii(v,u));
}
}
else if(g1[u].p != v){
g1[u].low = min(g1[u].low, g1[v].depth);
}
}
}
class UFDS{
public:
vector<int> rak;
vector<int> p;
int n;
int numSets;
void create(int nn){
n = nn;
numSets = n;
for(int i = 0;i < n;i++){
rak.push_back(0);
p.push_back(i);
}
}
int findSet(int i){
if(i == p[i]) return i;
else{
p[i] = findSet(p[i]);
return p[i];
}
}
void unionSet(int a, int b){
int x = findSet(a);
int y = findSet(b);
if(x == y) return;
numSets--;
if(rak[x] < rak[y]){
p[x] = y;
}
else{
p[y] = x;
if(rak[x] == rak[y]) rak[x]++;
}
}
};
set<ii> nondupl;
set<ii> duplicates;
vector<pair<ii, int> > edgeIndex;
vector<node> tree;
void root(int u){
if(tree[u].vis) return;
tree[u].vis = true;
for(int i = 0;i < tree[u].adj.size();i++){
int v = tree[u].adj[i];
if(tree[v].vis) continue;
tree[v].depth = tree[u].depth + 1;
tree[v].p = u;
root(v);
}
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
int main()
{
//freopen("i.txt","r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
UFDS overall;
overall.create(n);
for(int i = 0;i < m;i++){
int a, b;
cin >> a >> b;
a--;
b--;
overall.unionSet(a,b);
g1[a].adj.push_back(b);
g1[b].adj.push_back(a);
if(nondupl.find(ii(a,b)) == nondupl.end()){
nondupl.insert(ii(a,b));
}
else{
duplicates.insert(ii(a,b));
}
if(nondupl.find(ii(b,a)) == nondupl.end()){
nondupl.insert(ii(b,a));
}
else{
duplicates.insert(ii(b,a));
}
edgeIndex.push_back(make_pair(ii(a,b),i));
}
if(overall.numSets != 1) return 1;
for(int i = 0;i < n;i++){
if(!g1[i].vis){
g1[i].depth = 0;
dfs(i);
}
}
for(ii x : bridges){
//cout << x.first << " " << x.second << "\n";
}
///creating the bridge tree
UFDS ufds;
ufds.create(n);
for(int i = 0;i < n;i++){
for(int j = 0;j < g1[i].adj.size();j++){
ii x = ii(i, g1[i].adj[j]);
if(duplicates.find(x) != duplicates.end() || bridges.find(x) == bridges.end()){
ufds.unionSet(x.first,x.second);
}
}
}
//cout << ufds.findSet(0) << ufds.findSet(1);
set<int> coms;
int id[n];
fill(id,id+n,-1);
for(int i = 0;i < n;i++){
if(coms.find(ufds.findSet(i)) != coms.end()) continue;
else{
id[ufds.findSet(i)] = coms.size();
coms.insert(ufds.findSet(i));
node kkkk;
tree.push_back(kkkk);
}
}
for(int i = 0;i < n;i++){
//cout << id[i] << " ";
}
//cout << "\n";
set<ii> edges;
for(int i = 0;i < n;i++){
for(int j = 0;j < g1[i].adj.size();j++){
int u = i;
int v = g1[i].adj[j];
u = id[ufds.findSet(u)];
v = id[ufds.findSet(v)];
if(u != v){
if(v > u) swap(u,v);
edges.insert(ii(u,v));
}
}
}
for(ii x : edges){
//cout << x.first << " " << x.second << "\n";
tree[x.first].adj.push_back(x.second);
tree[x.second].adj.push_back(x.first);
}
int nn = tree.size();
for(int i =0;i < nn;i++){
if(!tree[i].vis){
//cout << i << "\n";
tree[i].depth = 0;
root(i);
}
}
for(int i = 0;i < nn;i++){
//cout << tree[i].depth << " ";
}
//cout << "\n";
int p = 0;
cin >> p;
for(int qq = 0;qq < p;qq++){
int a, b;
cin >> a >> b;
a--;
b--;
a = id[ufds.findSet(a)];
b = id[ufds.findSet(b)];
while(a != b){
if(tree[a].depth > tree[b].depth){
tree[a].up = 1;
a = tree[a].p;
}
else{
tree[b].up = 2;
b = tree[b].p;
}
}
}
for(int i = 0;i < nn;i++){
//cout << tree[i].up << " ";
}
//cout << "\n";
//cout << '\n';
//cout << '\n';
int ans[n];
for(int i = 0;i < m;i++){
ans[i] = 0;
}
for(int i = 0;i < m;i++){
ii x = edgeIndex[i].first;
int y = edgeIndex[i].second;
//cout << x.first << " " << x.second << " " << y << "\n";
if(duplicates.find(x) != duplicates.end() || bridges.find(x) == bridges.end()){
ans[i] = 4;
continue;
}
else{
int u = id[ufds.findSet(x.first)];
int v = id[ufds.findSet(x.second)];
if(abs(tree[u].depth - tree[v].depth) > 1) return 1;
//cout << u << " " << v << " ";
if(tree[u].depth > tree[v].depth){ ///u -> v
ans[i] = tree[u].up;
//cout << tree[u].up << " u\n";
}
else{ ///v -> u
ans[i] = 3 - tree[v].up;
//cout << tree[v].up << " v\n";
}
}
}
for(int i = 0;i < m;i++){
//cout << ans[i] << " ";
if(ans[i] == 1) cout << "R";
else if(ans[i] == 2) cout << "L";
else if(ans[i] == 4) cout << "X";
else cout << "B";
}
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs(int)':
oneway.cpp:23:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < g1[u].adj.size();i++){
~~^~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void root(int)':
oneway.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < tree[u].adj.size();i++){
~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:153:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
for(ii x : bridges){
^
oneway.cpp:163:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < g1[i].adj.size();j++){
~~^~~~~~~~~~~~~~~~~~
oneway.cpp:194:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < g1[i].adj.size();j++){
~~^~~~~~~~~~~~~~~~~~
oneway.cpp:262:13: warning: unused variable 'y' [-Wunused-variable]
int y = edgeIndex[i].second;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4984 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4984 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4984 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
