#include <iostream>
#include <set>
#include <vector>
#include <queue>
using namespace std;
/*
For all pairs (x, y)
If all possible routes from x to y have one or more roads in common, all such roads must be directed.
Repeatedly until there is at least one node with degree = 1:
1. Find a node with degree = 1
2. If that node has no x(+) or y(-) points, set its only edge to 'B'
3. Add all that node's + and - points to a set. Use DSU-style algoithm to combine the sets of its children.
Depending on this, set the direction for its parent edge.
After there are no more nodes with degree = 1, set all remaining edges to 'B'
*/
int main()
{
int n, m;
cin >> n >> m;
vector<char> res(m+1, 'B');
vector<int> edge[n+1];
vector<int> edge_count(n+1, 0);
int a[m+1], b[m+1];
for(int i = 1; i <= m; i++)
{
cin >> a[i] >> b[i];
edge[a[i]].push_back(i);
edge_count[a[i]]++;
edge[b[i]].push_back(i);
edge_count[b[i]]++;
}
int p;
cin >> p;
vector<int> endpoints(n+1, 0);
int x, y;
for(int i = 1; i <= p; i++)
{
cin >> x >> y;
endpoints[x]++;
endpoints[y]--;
}
queue<int> tbv;
for(int i = 1; i <= n; i++)
if(edge_count[i] == 1)
tbv.push(i);
int curr;
int parent_edge;
int parent;
while(!tbv.empty())
{
curr = tbv.front();
tbv.pop();
edge_count[curr]--;
for(int e: edge[curr])
{
if(edge_count[a[e] + b[e] - curr] == 0) endpoints[curr] += endpoints[a[e] + b[e] - curr];
else parent_edge = e;
}
parent = a[parent_edge] + b[parent_edge] - curr;
if(endpoints[curr] > 0)
{
if(a[parent_edge] == curr) res[parent_edge] = 'R';
else res[parent_edge] = 'L';
}
else if(endpoints[curr] < 0)
{
if(a[parent_edge] == curr) res[parent_edge] = 'L';
else res[parent_edge] = 'R';
}
edge_count[parent]--;
if(edge_count[parent] == 1) tbv.push(parent);
}
for(int i = 1; i <= m; i++) cout << res[i];
cout << '\n';
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:69:9: warning: 'parent_edge' may be used uninitialized in this function [-Wmaybe-uninitialized]
69 | int parent_edge;
| ^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
