fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. static const int MAXN = 100000;
  7. int n, m, t;
  8. vector<int> g[MAXN+1], gr[MAXN+1], buc[MAXN+1];
  9. int parent[MAXN+1], semi[MAXN+1], idom[MAXN+1], dsu[MAXN+1], label[MAXN+1], dfn[MAXN+1], revord[MAXN+1];
  10.  
  11. void dfs(int u) {
  12. t++;
  13. dfn[u] = t;
  14. revord[t] = u;
  15. label[u] = u;
  16. semi[u] = t;
  17. dsu[u] = u;
  18. for (int w: g[u]) {
  19. if (!dfn[w]) {
  20. parent[w] = u;
  21. dfs(w);
  22. }
  23. gr[w].push_back(u);
  24. }
  25. }
  26.  
  27. int findr(int v) {
  28. if (dsu[v] == v) return v;
  29. int p = findr(dsu[v]);
  30. if (semi[label[dsu[v]]] < semi[label[v]]) label[v] = label[dsu[v]];
  31. return dsu[v] = p;
  32. }
  33.  
  34. void unite(int u, int v) {
  35. dsu[v] = u;
  36. }
  37.  
  38. int main() {
  39. ios::sync_with_stdio(false);
  40. cin.tie(nullptr);
  41.  
  42. cin >> n >> m;
  43. for (int i = 0; i < m; i++) {
  44. int a, b;
  45. cin >> a >> b;
  46. g[a].push_back(b);
  47. }
  48.  
  49. dfs(1);
  50. for (int i = t; i >= 2; i--) {
  51. int w = revord[i], p = parent[w];
  52. for (int v: gr[w]) {
  53. if (dfn[v]) {
  54. findr(v);
  55. if (semi[label[v]] < semi[w]) semi[w] = semi[label[v]];
  56. }
  57. }
  58. buc[revord[semi[w]]].push_back(w);
  59. unite(p, w);
  60. for (int v: buc[p]) {
  61. findr(v);
  62. if (semi[label[v]] < semi[p]) idom[v] = label[v];
  63. else idom[v] = p;
  64. }
  65. buc[p].clear();
  66. }
  67. for (int i = 2; i <= t; i++) {
  68. int w = revord[i];
  69. if (idom[w] != revord[semi[w]]) idom[w] = idom[idom[w]];
  70. }
  71. idom[1] = 1;
  72.  
  73. vector<bool> isDom(n+1,false);
  74. int x = n;
  75. while (x && !isDom[x]) {
  76. isDom[x] = true;
  77. x = idom[x];
  78. if (x == 0) break;
  79. }
  80.  
  81. vector<int> ans;
  82. for (int i = 1; i <= n; i++) {
  83. if (isDom[i]) ans.push_back(i);
  84. }
  85. cout << ans.size() << "\n";
  86. for (int i = 0; i < (int)ans.size(); i++) {
  87. cout << ans[i];
  88. if (i+1 < (int)ans.size()) cout << " ";
  89. }
  90. cout << "\n";
  91.  
  92. return 0;
  93. }
Success #stdin #stdout 0.01s 11588KB
stdin
Standard input is empty
stdout
0