fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8. #define mp make_pair
  9.  
  10. using namespace std;
  11.  
  12. struct Node
  13. {
  14.     int top, idx, dist;
  15.  
  16.     Node(int top = 0, int idx = 0, int dist = 0) :
  17.         top(top), idx(idx), dist(dist) {};
  18. };
  19.  
  20. const int maxn = 2e5;
  21. const int INF = 1e9;
  22.  
  23. int t, n, m, q, id[maxn + 10], low[maxn + 10], timer = 0;
  24. ii ans[maxn + 10];
  25. vector<ii> adj[maxn + 10];
  26. queue<Node> qe;
  27.  
  28. bool dfs(int top, int p = -1)
  29. {
  30.     bool is_par_n = 0;
  31.     id[top] = low[top] = ++timer;
  32.     for (ii pr : adj[top])
  33.     {
  34.         int next_top = pr.fi;
  35.         int idx = pr.se;
  36.         if (next_top == p)
  37.             continue;
  38.         if (id[next_top])
  39.             low[top] = min(low[top], id[next_top]);
  40.         else
  41.         {
  42.             bool flag = dfs(next_top, top);
  43.             is_par_n |= flag;
  44.             low[top] = min(low[next_top], low[top]);
  45.             if (low[next_top] == id[next_top] && flag)
  46.             {
  47.                 qe.push(Node(top, idx, 0));
  48.                 qe.push(Node(next_top, idx, 0));
  49.                 ans[top] = min(ans[top], {0, idx});
  50.                 ans[next_top] = min(ans[next_top], {0, idx});
  51.             }
  52.         }
  53.     }
  54.     return is_par_n || top == n;
  55. }
  56.  
  57. int main()
  58. {
  59.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  60.     if (fopen("F.INP", "r"))
  61.     {
  62.         freopen("F.INP", "r", stdin);
  63.         freopen("F.OUT", "w", stdout);
  64.     }
  65.  
  66.     cin >> t;
  67.     while (t--)
  68.     {
  69.         timer = 0;
  70.         cin >> n >> m;
  71.         while (qe.size())
  72.             qe.pop();
  73.         for (int i = 1; i <= n; i++)
  74.         {
  75.             adj[i].clear();
  76.             id[i] = low[i] = 0;
  77.             ans[i] = {INF, -1};
  78.         }
  79.         for (int i = 1; i <= m; i++)
  80.         {
  81.             int x, y;
  82.             cin >> x >> y;
  83.             adj[x].push_back({y, i});
  84.             adj[y].push_back({x, i});
  85.         }
  86.         dfs(1);
  87.         while (qe.size())
  88.         {
  89.             Node t = qe.front();
  90.             qe.pop();
  91.             int top = t.top;
  92.             int dist = t.dist;
  93.             int idx = t.idx;
  94.             if (dist > ans[top].fi)
  95.                 continue;
  96.             for (ii pr : adj[top])
  97.             {
  98.                 int next_top = pr.fi;
  99.                 if (ans[next_top] > mp(ans[top].fi + 1, ans[top].se))
  100.                 {
  101.                     ans[next_top] = {ans[top].fi + 1, ans[top].se};
  102.                     qe.push(Node(next_top, ans[next_top].se, ans[next_top].fi));
  103.                 }
  104.             }
  105.         }
  106.         cin >> q;
  107.         for (int i = 1; i <= q; i++)
  108.         {
  109.             int x;
  110.             cin >> x;
  111.             cout << ans[x].se << ' ';
  112.         }
  113.         el;
  114.     }
  115. }
  116.  
Success #stdin #stdout 0.01s 9216KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BAAOFZ
language:
C++14 (gcc 8.3)
created:
15 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!