fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. using pii = pair<int, int>;
  7. const int N = 3e5 + 5;
  8. const int LG = 19;
  9. int n, m, q;
  10. vector<int> G[N];
  11.  
  12. namespace BridgeType{
  13. vector<int> g[N], stk;
  14. int color[N], low[N], num[N], stt = 0, scc = 0;
  15.  
  16. int h[N], up[N][LG];
  17. void dfs(int u, int pre) {
  18.     num[u] = low[u] = ++stt;
  19.     stk.push_back(u);
  20.     for (int v: G[u]) {
  21.         if (v == pre) {
  22.             pre = 0;
  23.             continue;
  24.         }
  25.         if (!num[v]) {
  26.             dfs(v, u);
  27.             low[u] = min(low[u], low[v]);
  28.             if (low[v] > num[u]) {
  29.                 int i;
  30.                 ++scc;
  31.                 do {
  32.                     i = stk.back(); stk.pop_back();
  33.                     color[i] = scc;
  34.                 } while(i != v);
  35.             }
  36.         }
  37.         else low[u] = min(low[u], num[v]);
  38.     }
  39. }
  40.  
  41. void buildGraph() {
  42.     for (int u = 1; u <= n; u++) {
  43.         for (int v: G[u]) if (color[u] != color[v]) {
  44.             g[color[u]].push_back(color[v]);
  45.         }
  46.     }
  47. }
  48. void dfsLca(int u) {
  49.     for (int v: g[u]) if (v != up[u][0]) {
  50.         h[v] = h[u] + 1;
  51.         up[v][0] = u;
  52.         for (int lg = 1; lg < LG; lg++) up[v][lg] = up[up[v][lg - 1]][lg - 1];
  53.         dfsLca(v);
  54.     }
  55. }
  56. int lca(int u, int v) {
  57.     if (h[u] != h[v]) {
  58.         if (h[u] < h[v]) swap(u, v);
  59.         int k = h[u] - h[v]; 
  60.         for (int lg = 0; (1 << lg) <= k; lg++) {
  61.             if (k >> lg & 1) u = up[u][lg];
  62.         }
  63.     }
  64.     if (u == v) return u;
  65.     for (int lg = __lg(h[u]); lg >= 0; lg--) {
  66.         if (up[u][lg] != up[v][lg]) {
  67.             u = up[u][lg];
  68.             v = up[v][lg];
  69.         }
  70.     }
  71.     return up[u][0];
  72. }
  73. int getPath(int u, int v) {
  74.     int p = lca(u, v);
  75.     return h[u] + h[v] - 2 * h[p];
  76. }
  77. int query(int a, int b) {
  78.     return getPath(color[a], color[b]);
  79. }
  80. void init() {
  81.     for (int u = 1; u <= n; u++) {
  82.         if (!num[u]) {
  83.             dfs(u, -1);
  84.             int i;
  85.             ++scc;
  86.             do {
  87.                 i = stk.back(); stk.pop_back();
  88.                 color[i] = scc;
  89.             } while(i != u);
  90.  
  91.         }
  92.     }
  93.     buildGraph();
  94.     for (int lg = 0; lg < LG; lg++) up[1][lg] = 1;
  95.     dfsLca(1);
  96. }
  97. };
  98.  
  99. namespace APType{
  100. vector<int> g[N], stk;
  101. vector<int> Group[N];
  102. int color[N], low[N], num[N], stt = 0, scc = 0;
  103. int AP[N];
  104. int sz = 0;
  105.  
  106. int h[N], up[N][LG];
  107. int on[N], val[N];
  108. void dfs(int u, int pre) {
  109.     num[u] = low[u] = ++stt;
  110.     stk.push_back(u);
  111.     for (int v: G[u]) {
  112.         if (v == pre) continue;
  113.  
  114.         if (!num[v]) {
  115.             dfs(v, u);
  116.             low[u] = min(low[u], low[v]);
  117.             if (low[v] >= num[u]) {
  118.                 if (num[u] > 1 || num[v] > 2) AP[u] = 1;
  119.                 ++scc;
  120.                 Group[scc].push_back(u);
  121.                 int t;
  122.                 do {
  123.                     t = stk.back(); stk.pop_back();
  124.                     Group[scc].push_back(t);
  125.                 } while(t != v);
  126.             }
  127.         }
  128.         else low[u] = min(low[u], num[v]);
  129.     }
  130. }
  131. void buildTree() {
  132.     for (int u = 1; u <= n; u++) {
  133.         if (AP[u]) color[u] = ++sz;
  134.     }
  135.     for (int id = 1; id <= scc; id++) { // Worst case scc eqqual n + m, so Color[N + M];
  136.         int U = ++sz;
  137.         for (int u: Group[id]) {
  138.             if (!AP[u]) color[u] = U;
  139.             else {
  140.                 g[U].push_back(color[u]);
  141.                 g[color[u]].push_back(U);
  142.             }
  143.         }
  144.     }
  145. }
  146. void dfsLca(int u) {
  147.     val[u] += on[u];
  148.     for (int v: g[u]) if (v != up[u][0]) {
  149.         h[v] = h[u] + 1;
  150.         up[v][0] = u;
  151.         for (int lg = 1; lg < LG; lg++) up[v][lg] = up[up[v][lg - 1]][lg - 1];
  152.         val[v] = val[u];
  153.         dfsLca(v);
  154.     }
  155. }
  156. int lca(int u, int v) {
  157.     if (h[u] != h[v]) {
  158.         if (h[u] < h[v]) swap(u, v);
  159.         int k = h[u] - h[v]; 
  160.         for (int lg = 0; (1 << lg) <= k; lg++) {
  161.             if (k >> lg & 1) u = up[u][lg];
  162.         }
  163.     }
  164.     if (u == v) return u;
  165.     for (int lg = __lg(h[u]); lg >= 0; lg--) {
  166.         if (up[u][lg] != up[v][lg]) {
  167.             u = up[u][lg];
  168.             v = up[v][lg];
  169.         }
  170.     }
  171.     return up[u][0];
  172. }
  173. int getPath(int u, int v) {
  174.     int p = lca(u, v);
  175.     return val[u] + val[v] - 2 * val[p] + on[p];
  176. }
  177. int query(int a, int b) {
  178.     return getPath(color[a], color[b]) + !AP[a] + !AP[b];
  179. }
  180. void init() {
  181.     for (int u = 1; u <= n; u++) {
  182.         if (!num[u]) dfs(u, -1);
  183.     }
  184.     buildTree();
  185.     for (int i = 1; i <= n; i++) if (AP[i]) on[color[i]] = 1;
  186.     for (int i = 1; i <= sz; i++) if (!up[i][0]) {
  187.         for (int lg = 0; lg < LG; lg++) up[i][lg] = i;
  188.         dfsLca(i);
  189.     }
  190. }
  191. };
  192.  
  193. signed main() {
  194.     cin.tie(NULL)->sync_with_stdio(false);
  195.     if(ifstream("CNET.inp")) {
  196.         freopen("CNET.inp", "r", stdin);
  197.         freopen("CNET.out", "w", stdout);
  198.     }
  199.     cin >> n >> m;
  200.     for (int i = 1; i <= m; i++) {
  201.         int u, v;
  202.         cin >> u >> v;
  203.         G[u].push_back(v);
  204.         G[v].push_back(u);
  205.     }
  206.     BridgeType::init();
  207.     APType::init();
  208.     cin >> q;
  209.     while(q--) {
  210.         int a, b; cin >> a >> b;
  211.         cout << APType::query(a, b) << " " << BridgeType::query(a, b) << "\n";
  212.     }
  213.     return 0;
  214. }
Success #stdin #stdout 0.02s 35496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TdRcsu
language:
C++14 (gcc 8.3)
created:
3 days 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!