fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  5. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  6. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  7. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  8. #define SZ(S) ((int) ((S).size()))
  9.  
  10. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  11. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  12. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  13.  
  14. vector< int > G[10111];
  15. int V;
  16.  
  17. struct UndirectedDfs {
  18.     vector<int> low, num, parent;
  19.     vector<bool> articulation;
  20.     int counter, root, children;
  21.  
  22.     vector< pair<int,int> > bridges;
  23.     vector<int> cuts;
  24.  
  25.     UndirectedDfs() : low(V, 0), num(V, -1), parent(V, 0), articulation(V, false),
  26.             counter(0), children(0) {
  27.         for(int i = 0; i < V; ++i) if (num[i] == -1) {
  28.             root = i; children = 0;
  29.             dfs(i);
  30.             articulation[root] = (children > 1);
  31.         }
  32.         for(int i = 0; i < V; ++i)
  33.             if (articulation[i]) cuts.push_back(i);
  34.     }
  35. private:
  36.     void dfs(int u) {
  37.         low[u] = num[u] = counter++;
  38.         for(int j = 0; j < G[u].size(); ++j) {
  39.             int v = G[u][j];
  40.             if (num[v] == -1) {
  41.                 parent[v] = u;
  42.                 if (u == root) children++;
  43.                 dfs(v);
  44.                 if (low[v] >= num[u])
  45.                     articulation[u] = true;
  46.                 if (low[v] > num[u]) bridges.push_back(make_pair(u, v));
  47.                 low[u] = min(low[u], low[v]);
  48.             } else if (v != parent[u])
  49.                 low[u] = min(low[u], num[v]);
  50.         }
  51.     }
  52. };
  53.  
  54. int lab[10111];
  55.  
  56. int getRoot(int u) {
  57.     if (lab[u] < 0) return u;
  58.     return lab[u] = getRoot(lab[u]);
  59. }
  60. void merge(int u, int v) {
  61.     u = getRoot(u); v = getRoot(v);
  62.     if (u == v) return ;
  63.     lab[u] = lab[u] + lab[v];
  64.     lab[v] = u;
  65. }
  66.  
  67. int main() {
  68.     ios :: sync_with_stdio(false); cin.tie(NULL);
  69.     cout << (fixed) << setprecision(6);
  70.     int n, m, q;
  71.     while (cin >> n >> m >> q && n) {
  72.         V = n;
  73.         REP(i,n) G[i].clear();
  74.         FOR(i,1,m) {
  75.             int u, v; cin >> u >> v;
  76.             --u; --v;
  77.             G[u].push_back(v);
  78.             G[v].push_back(u);
  79.         }
  80.         UndirectedDfs tree;
  81.         memset(lab, -1, sizeof lab);
  82.         for(auto p : tree.bridges) {
  83.             int u = p.first, v = p.second;
  84.             ++u; ++v;
  85.             merge(u, v);
  86.         }
  87.  
  88.         while (q--) {
  89.             int u, v; cin >> u >> v;
  90.             if (getRoot(u) == getRoot(v)) cout << 'Y';
  91.             else cout << 'N';
  92.             cout << "\n";
  93.         }
  94.         cout << "-\n";
  95.     }
  96.     return 0;
  97. }
  98.  
  99.  
Success #stdin #stdout 0s 3640KB
comments (?)
stdin
copy 
6 5 3
1 2
2 3
2 4
2 5
4 5
1 3
1 5
2 6
4 2 3
1 2
2 3
1 4
1 3
1 2
0 0 0
stdout
copy 
Y
N
N
-
N
Y
Y
-
https://ideone.com/RvuuND
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!