Advertisement
Guest User

Untitled

a guest
Dec 10th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <queue>
  5.  
  6. using namespace std;
  7. vector <vector <int> > graph;
  8. vector <bool> used;
  9.  
  10. void dfs (int i) {
  11. used[i] = true;
  12. for (int j = 0; j < graph[i].size(); ++j) {
  13. if (!used[graph[i][j]]) {
  14. dfs(graph[i][j]);
  15. }
  16. }
  17. }
  18.  
  19. bool checkGraph (int n) {
  20. for (int i = 0; i < n; ++i) {
  21. if (!used[i])
  22. return 0;
  23. }
  24. return 1;
  25. }
  26.  
  27. int main(int argc, const char * argv[]) {
  28. ifstream fin("/Users/ilabockov/Desktop/xcode/SWIFT/SwiftBook/graphs/graphs/input.txt");
  29. ofstream fout("/Users/ilabockov/Desktop/xcode/SWIFT/SwiftBook/graphs/graphs/output.txt");
  30. int n;
  31. int maxTime (0), firstDomino;
  32. fin >> n;
  33. graph.resize(n);
  34. used.resize(n);
  35. for (int i = 0; i < n; ++i) {
  36. int m;
  37. fin >> m;
  38. for (int i = 0; i < m; ++i) {
  39. int buf;
  40. fin >> buf;
  41. graph[i].push_back(buf - 1);
  42. }
  43. }
  44. fin.close();
  45.  
  46. dfs(0);
  47. for (int i = 0; i < n; ++i) {
  48. if (!used[i]) {
  49. fout << "impossible";
  50. fout.close();
  51. return 0;
  52. }
  53. used[i] = false;
  54. }
  55.  
  56. int flag = 0;
  57. for (int i = 0; i < n; ++i) {
  58. int time = 0;
  59. // queue <int> myQueue;
  60. // if (!used[i]) {
  61. // myQueue.push(i);
  62. // used[i] = true;
  63. // while (!myQueue.empty()) {
  64. // int i = myQueue.front();
  65. // myQueue.pop();
  66. // for (int j = 0; j < graph[i].size(); ++j) {
  67. // if (!used[graph[i][j]]) {
  68. // myQueue.push(graph[i][j]);
  69. // used[graph[i][j]] = true;
  70. // time ++;
  71. // } else time --;
  72. // }
  73. // }
  74. // }
  75. queue <int> myQueue;
  76. myQueue.push(i);
  77. used[i] = true;
  78. while (true) {
  79. queue <int> bufQueue;
  80. while (!myQueue.empty()) {
  81. int i = myQueue.front();
  82. myQueue.pop();
  83. for (int j = 0; j < graph[i].size(); ++j) {
  84. if (!used[graph[i][j]]) {
  85. bufQueue.push(graph[i][j]);
  86. used[graph[i][j]] = true;
  87. }
  88. }
  89. }
  90. if (bufQueue.empty()) {
  91. break;
  92. }
  93. time++;
  94. myQueue = bufQueue;
  95. }
  96.  
  97. if (time >= maxTime && checkGraph(n)) {
  98. maxTime = time;
  99. firstDomino = i;
  100. flag = 1;
  101. }
  102. for (int i = 0; i < n; ++i) {
  103. used[i] = false;
  104. }
  105. }
  106. if (flag == 1) {
  107. fout << maxTime << endl << firstDomino + 1;
  108. } else {
  109. fout << "impossible";
  110. }
  111. fout.close();
  112. return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement