Guest User

Untitled

a guest
Feb 19th, 2020
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.85 KB | None | 0 0
  1. typedef long long ll;
  2. typedef vector<int> vi;
  3. typedef vector<ll> vll;
  4. typedef vector<vector<int> > vvi;
  5. typedef pair<int, int> ii;
  6. typedef vector<pair<int, int> > vii;
  7. typedef vector<vector<pair<int, int> > > vvii;
  8.  
  9.  
  10. #define all(x) (x).begin(), (x).end()
  11. #define nall(x) (x).rbegin(), (x).rend()
  12. #define sz(a) int((a).size())
  13. #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  14. #define pb push_back
  15. #define rz resize
  16. #define MP make_pair
  17. #define F first
  18. #define S second
  19. #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
  20. #define NFOR(i,a,b) for(int i=(a);i>=(b);--i)
  21. #define TCASE int __T;cin>>__T;FOR(Tc,1,__T)
  22.  
  23.  
  24.  
  25. struct dis_set
  26. {
  27. vi p, r;
  28. dis_set() {}
  29. dis_set(int n): p(n), r(n) {FOR(i, 0, n - 1)p[i] = i;}
  30.  
  31. int get(int i)
  32. {
  33. if (p[i] != i)p[i] = get(p[i]);
  34. return p[i];
  35. }
  36. int connect(int i, int j)
  37. {
  38. int x = get(i), y = get(j);
  39. if (x == y) return 0;
  40. if (r[x] < r[y])p[x] = y;
  41. else {p[y] = x; if (r[x] == r[y])++r[x];}
  42. return 1;
  43. }
  44. };
  45.  
  46. struct BlockCutTree {
  47. vector<vector<pair<int, int> > > g;
  48.  
  49. int n, m, dfsctr, root, child;
  50. vi dfs_num, dfs_low, depth, vis, is_art, low;
  51. vector<ii> e;
  52. dis_set edges;
  53. vvi blocks, toArt, inBlock;
  54.  
  55. // special :
  56. vi here, ans, reached;
  57. vvi VIS;
  58.  
  59.  
  60. void dfs_pre(int u, int p, int e)
  61. {
  62. dfs_num[u] = dfs_low[u] = dfsctr++;
  63. low[u] = depth[u];
  64. for (auto it : g[u])
  65. {
  66. if (dfs_num[it.F] == -1)
  67. {
  68. depth[it.F] = depth[u] + 1;
  69. if (u == root)++child;
  70. dfs_pre(it.F, u, it.S);
  71. dfs_low[u] = min(dfs_low[u], dfs_low[it.F]);
  72. low[u] = min(low[u], low[it.F]);
  73. if (dfs_low[it.F] >= dfs_num[u])
  74. is_art[u] = 1;
  75. if (e != -1)if (low[it.F] < depth[u]) edges.connect(e, it.S);
  76. }
  77. else if (p != it.F)
  78. {
  79. if (e != -1)if (dfs_num[it.F] < dfs_num[u]) edges.connect(e, it.S);
  80. low[u] = min(low[u], depth[it.F]);
  81. dfs_low[u] = min(dfs_low[u], dfs_num[it.F]);
  82. }
  83. }
  84. }
  85.  
  86. BlockCutTree (vvii &ig, int m): g(ig), m(m) { // pair<to, edge_index>
  87. n = ig.size();
  88.  
  89. e = vector<ii>(m);
  90. FOR (i, 0, n - 1) for (ii it : g[i]) e[it.S] = {i, it.F};
  91.  
  92. low = is_art = dfs_low = depth = vis = vi(n);
  93. dfs_num = vi(n, -1);
  94.  
  95. dfsctr = 0;
  96. root = 0, child = 0;
  97. edges = dis_set(m);
  98. dfs_pre(0, -1, -1);
  99. is_art[root] = child > 1;
  100.  
  101. blocks = vvi(m);
  102.  
  103. FOR (i, 0, m - 1) {
  104. blocks[edges.get(i)].pb(e[i].F);
  105. blocks[edges.get(i)].pb(e[i].S);
  106. }
  107.  
  108. FOR (i, 0, m - 1) {
  109. sort(all(blocks[i]));
  110. blocks[i].erase(unique(all(blocks[i])), blocks[i].end());
  111. }
  112. toArt.resize(m), inBlock.resize(n);
  113.  
  114. FOR (i, 0, m - 1) {
  115. for (int it : blocks[i]) {
  116. inBlock[it].pb(i);
  117. if (is_art[it]) {
  118. toArt[i].pb(it);
  119. }
  120. }
  121. }
  122.  
  123. }
  124.  
  125. void dfs(int u, bool isBlock) {
  126. if (isBlock and reached[u]) {
  127. ans = here;
  128. return;
  129. }
  130. VIS[u][isBlock] = 1;
  131.  
  132. if (isBlock) {
  133. FOR (i, 0, sz(toArt[u]) - 1) {
  134. int v = toArt[u][i];
  135. if (!VIS[v][0]) {
  136. dfs(v, 0);
  137. }
  138. }
  139. }
  140. else {
  141. here.pb(u);
  142. FOR (i, 0, sz(inBlock[u]) - 1) {
  143. int v = inBlock[u][i];
  144. if (!VIS[v][1]) {
  145. dfs(v, 1);
  146. }
  147. }
  148. here.pop_back();
  149. }
  150. }
  151.  
  152. void solve(int s, int e) {
  153. reached = vi(m);
  154. FOR (i, 0, sz(inBlock[e]) - 1) {
  155. reached[inBlock[e][i]] = 1;
  156. }
  157. VIS = vvi (m, vi(2));
  158.  
  159. dfs(inBlock[s][0], 1);
  160.  
  161. if (find(all(ans), s) != ans.end())
  162. ans.erase(find(all(ans), s));
  163.  
  164. if (find(all(ans), e) != ans.end())
  165. ans.erase(find(all(ans), e));
  166.  
  167. cout << sz(ans) << "\n";
  168. sort(all(ans));
  169. FOR (i, 0, sz(ans) - 1) {
  170. cout << ans[i] + 1 << "\n";
  171. }
  172. }
  173. };
Add Comment
Please, Sign In to add comment