fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Edge { int u, v; };
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n, m; 
  11.     if (!(cin >> n >> m)) return 0;
  12.  
  13.     vector<Edge> E(m+1);
  14.     vector<vector<pair<int,int>>> g(n+1); // (to, edge_id)
  15.     for (int i = 1; i <= m; ++i) {
  16.         int a, b; cin >> a >> b;
  17.         E[i] = {a, b};
  18.         g[a].push_back({b, i});
  19.         g[b].push_back({a, i});
  20.     }
  21.  
  22.     int p; 
  23.     cin >> p;
  24.     vector<pair<int,int>> req(p);
  25.     for (int i = 0; i < p; ++i) cin >> req[i].first >> req[i].second;
  26.  
  27.     // -------- Tarjan: tìm cầu --------
  28.     vector<int> tin(n+1, 0), low(n+1, 0);
  29.     vector<char> isBridge(m+1, 0);
  30.     int timer = 0;
  31.     function<void(int,int)> dfs_bridge = [&](int u, int pe) {
  32.         tin[u] = low[u] = ++timer;
  33.         for (auto [v, id] : g[u]) {
  34.             if (id == pe) continue;
  35.             if (!tin[v]) {
  36.                 dfs_bridge(v, id);
  37.                 low[u] = min(low[u], low[v]);
  38.                 if (low[v] > tin[u]) isBridge[id] = 1;
  39.             } else {
  40.                 low[u] = min(low[u], tin[v]);
  41.             }
  42.         }
  43.     };
  44.     for (int i = 1; i <= n; ++i) if (!tin[i]) dfs_bridge(i, -1);
  45.  
  46.     // -------- Nén theo cạnh không phải cầu --------
  47.     vector<int> comp(n+1, -1);
  48.     int C = 0;
  49.     function<void(int)> dfs_comp = [&](int u) {
  50.         comp[u] = C;
  51.         for (auto [v, id] : g[u]) {
  52.             if (isBridge[id] || comp[v] != -1) continue;
  53.             dfs_comp(v);
  54.         }
  55.     };
  56.     for (int i = 1; i <= n; ++i) if (comp[i] == -1) { ++C; dfs_comp(i); }
  57.  
  58.     // -------- Xây cây cầu (bridge-tree) --------
  59.     vector<vector<pair<int,int>>> tree(C+1); // (toComp, edge_id original)
  60.     for (int id = 1; id <= m; ++id) if (isBridge[id]) {
  61.         int a = comp[E[id].u], b = comp[E[id].v];
  62.         if (a == b) continue; // an toàn
  63.         tree[a].push_back({b, id});
  64.         tree[b].push_back({a, id});
  65.     }
  66.  
  67.     // -------- Hiệu tuyến từ các yêu cầu x->y --------
  68.     vector<long long> sum(C+1, 0);
  69.     for (auto [x, y] : req) {
  70.         sum[comp[x]] += 1;
  71.         sum[comp[y]] -= 1;
  72.     }
  73.  
  74.     // -------- DFS cộng dồn & gán hướng cho các cầu --------
  75.     vector<char> ans(m+1, 'B');      // mặc định: cạnh trong chu trình -> 'B'
  76.     vector<char> vis(C+1, 0);
  77.     function<void(int,int)> dfs_tree = [&](int u, int parentEdge) {
  78.         vis[u] = 1;
  79.         for (auto [v, id] : tree[u]) {
  80.             if (id == parentEdge) continue;
  81.             if (!vis[v]) {
  82.                 dfs_tree(v, id);
  83.                 // Sau khi duyệt con v, quyết định hướng cho cầu id
  84.                 long long s = sum[v]; // tổng "luồng" cần đi qua cầu từ v lên u
  85.                 int cu = comp[E[id].u], cv = comp[E[id].v]; // comp của đầu mút theo cạnh gốc
  86.                 if (s > 0) {
  87.                     // cần hướng v -> u
  88.                     if (cu == v && cv == u)      ans[id] = 'L'; // a_i -> b_ielse if (cu == u && cv == v) ans[id] = 'R'; // b_i -> a_i
  89.                     else                          ans[id] = 'B'; // đề phòng (không xảy ra)
  90.                 } else if (s < 0) {
  91.                     // cần hướng u -> v
  92.                     if (cu == u && cv == v)      ans[id] = 'L';
  93.                     else if (cu == v && cv == u) ans[id] = 'R';
  94.                     else                          ans[id] = 'B';
  95.                 } else {
  96.                     ans[id] = 'B'; // không bị ràng buộc
  97.                 }
  98.                 sum[u] += sum[v];
  99.             }
  100.         }
  101.     };
  102.     for (int i = 1; i <= C; ++i) if (!vis[i]) dfs_tree(i, -1);
  103.  
  104.     // -------- In kết quả theo thứ tự cạnh 1..m --------
  105.     string out; out.resize(m);
  106.     for (int i = 1; i <= m; ++i) {
  107.         if (!isBridge[i]) out[i-1] = 'B';
  108.         else               out[i-1] = ans[i];
  109.     }
  110.     cout << out << '\n';
  111.     return 0;
  112. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
stdout 
BBLBBR
https://ideone.com/EJUvWJ
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!