Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <algorithm>
  5. #include <stack>
  6.  
  7. using namespace std;
  8.  
  9. class Capcity {
  10. private:
  11. void dfs(
  12. vector<vector<int>>& graph,
  13. int root,
  14. vector<int>& indices,
  15. vector<vector<int>>& sccNodes,
  16. stack<int>& s,
  17. stack<int>& p,
  18. vector<int>& sccMap,
  19. int& index
  20. ) {
  21. // visited
  22. if (indices[root] >= 0) {
  23. return;
  24. }
  25. indices[root] = index;
  26. p.push(root);
  27. s.push(root);
  28. ++index;
  29. for (int next : graph[root]) {
  30. if (indices[next] < 0) {
  31. dfs(graph, next, indices, sccNodes, s, p, sccMap, index);
  32. } else if (sccMap[next] < 0) {
  33. while (indices[p.top()] > indices[next]) {
  34. p.pop();
  35. }
  36. }
  37. }
  38. if (root == p.top()) {
  39. vector<int> component;
  40. int size = sccNodes.size();
  41. int top = -1;
  42. do {
  43. top = s.top();
  44. s.pop();
  45. sccMap[top] = size;
  46. component.push_back(top);
  47. } while (top != root);
  48. p.pop();
  49. sccNodes.push_back(component);
  50. }
  51. }
  52. public:
  53. vector<int> pathBased(vector<vector<int>>& graph) {
  54. int n = graph.size();
  55. vector<int> indices(n, -1);
  56. stack<int> s;
  57. stack<int> p;
  58. vector<vector<int>> sccNodes;
  59. vector<int> sccMap(n, -1);
  60.  
  61. int index = 0;
  62. for (int i = 0; i < n; ++i) {
  63. dfs(graph, i, indices, sccNodes, s, p, sccMap, index);
  64. }
  65. int sccN = sccNodes.size();
  66.  
  67. vector<int> indegrees(n, 0);
  68.  
  69. vector<unordered_set<int>> sccGraph(sccN);
  70. for (int i = 0; i < n; ++i) {
  71. int from = sccMap[i];
  72. for (int x : graph[i]) {
  73. int to = sccMap[x];
  74. if (from != to) {
  75. sccGraph[from].insert(to);
  76. }
  77. }
  78. }
  79.  
  80. for (int i = 0; i < sccN; ++i) {
  81. for (int x : sccGraph[i]) {
  82. indegrees[x]++;
  83. }
  84. }
  85.  
  86. int headNode = -1;
  87. for (int i = 0; i < sccN; ++i) {
  88. if (indegrees[i] == 0) {
  89. if (headNode < 0) {
  90. headNode = i;
  91. } else {
  92. headNode = -1;
  93. break;
  94. }
  95. }
  96. }
  97.  
  98. if (headNode == -1) {
  99. return vector<int>();
  100. }
  101. vector<int>& result = sccNodes[headNode];
  102. sort(result.begin(), result.end());
  103. return result;
  104. }
  105. };
  106.  
  107. int main() {
  108. int n, m;
  109. cin >> n >> m;
  110. vector<vector<int>> graph(n);
  111. for (int i = 0; i < m; ++i) {
  112. int a, b;
  113. cin >> a >> b;
  114. --a;
  115. --b;
  116. graph[b].push_back(a);
  117. }
  118. vector<int> result = Capcity().pathBased(graph);
  119. cout << result.size() << endl;
  120. if (result.empty()) {
  121. return 0;
  122. }
  123. cout << (result[0] + 1);
  124. for (int i = 1; i < result.size(); ++i) {
  125. cout << " " << (result[i] + 1);
  126. }
  127. cout << endl;
  128. return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement