Advertisement
haufont

Untitled

Sep 5th, 2016
349
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. const int maxgr = 1e4 + 1;
  9. vector<int> gr[maxgr], antigr[maxgr], gr_component[maxgr], antigr_component[maxgr];
  10. set< pair<int, int> > vecsort, vecsort_component, rebra_component;
  11. int topsort[maxgr], topsort_component[maxgr], colorgr[maxgr];
  12. bool used[maxgr];
  13.  
  14.  
  15. void dfs_topsort(int& timer, int v) { // топологическая сортировка обычного графа
  16. used[v] = true;
  17. for (int i = 0; i < antigr[v].size(); ++i) {
  18. int to = antigr[v][i];
  19. if (!used[to]) {
  20. dfs_topsort(timer, to);
  21. }
  22. }
  23. topsort[v] = timer++;
  24. vecsort.insert(make_pair(-topsort[v], v)); // добавление элементов в упорядоченности по убыванию по топсорт
  25. }
  26.  
  27. void dfs_component_topsort(int& timer, int v) { // топологическая сортировка графа компонент сильной связаности
  28. used[v] = true;
  29. for (int i = 0; i < antigr_component[v].size(); ++i) {
  30. int to = antigr_component[v][i];
  31. if (!used[to]) {
  32. dfs_component_topsort(timer, to);
  33. }
  34. }
  35. topsort_component[v] = timer++;
  36. vecsort_component.insert(make_pair(-topsort_component[v], v));
  37. }
  38.  
  39. void dfs_component_rebra(int v, int color) {
  40. colorgr[v] = color;
  41. vecsort.erase(make_pair(-topsort[v], v)); // удаление элемента компоненты
  42. for (int i = 0; i < gr[v].size(); ++i) {
  43. int to = gr[v][i];
  44. if (!colorgr[to]) {
  45. dfs_component_rebra(to, color);
  46. }
  47. else if (colorgr[to] != color) {
  48. rebra_component.insert(make_pair(colorgr[v], colorgr[to]));
  49. }
  50. }
  51. }
  52.  
  53. void dfs_cradle_search(int v) {
  54. used[v] = true;
  55. vecsort_component.erase(make_pair(-topsort_component[v], v));
  56. for (int i = 0; i < antigr_component[v].size(); ++i) {
  57. int to = antigr_component[v][i];
  58. if (!used[to]) {
  59. dfs_cradle_search(to);
  60. }
  61. }
  62. }
  63.  
  64. int main() {
  65. int n, m;
  66. cin >> n >> m;
  67. int cur1, cur2;
  68. for (int i = 0; i < m; ++i) {
  69. cin >> cur1 >> cur2;
  70. cur1--;
  71. cur2--;
  72. gr[cur1].push_back(cur2);
  73. antigr[cur2].push_back(cur1);
  74. }
  75. int timer = 0;
  76. for (int i = 0; i < n; ++i) {
  77. if (!used[i]) {
  78. dfs_topsort(timer, i); // топологическая сортировка
  79. }
  80. }
  81. memset(used, 0, sizeof(used));
  82. vector<int> col_ver(1, -1);
  83. int color = 1;
  84. while (vecsort.size() > 0) {
  85. col_ver.push_back(vecsort.begin()->second); // добавление вершины за основу компоненты
  86. dfs_component_rebra(vecsort.begin()->second, color);
  87. color++;
  88. }
  89. memset(used, 0, sizeof(used));
  90. for (auto curr : rebra_component) {
  91. gr_component[curr.first].push_back(curr.second);
  92. antigr_component[curr.second].push_back(curr.first);
  93. }
  94. timer = 0;
  95. for (int i = 1; i < color; ++i) {
  96. if (!used[i]) {
  97. dfs_component_topsort(timer, i);
  98. }
  99. }
  100. memset(used, 0, sizeof(used));
  101. set<int> cradle; // количество истоков
  102. while (vecsort_component.size() > 0) {
  103. cradle.insert(col_ver[vecsort_component.begin()->second]);
  104. dfs_cradle_search(vecsort_component.begin()->second);
  105. }
  106. cout << cradle.size() << endl;
  107. for (auto curr : cradle) {
  108. cout << curr + 1 << ' ';
  109. }
  110. return 0;
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement