Advertisement
Guest User

Untitled

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