fork download
  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
stdin
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
Y
N
N
-
N
Y
Y
-