Advertisement
Guest User

Untitled

a guest
May 26th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector<int> find_the_least(int n, bool *graph)
  6. {
  7. bool flag = true;
  8. vector<int> ans;
  9. for(int i = 0; i < n; i++)
  10. {
  11. for(int j = 0; j < n; j++)
  12. {
  13. if(graph[j * n + i])
  14. {
  15. flag = false;
  16. break;
  17. }
  18. }
  19. if(flag)
  20. ans.push_back(i);
  21. flag = true;
  22. }
  23. return ans;
  24. }
  25.  
  26. void create_string(int n, bool *graph, vector<vector<int> > *allPaths, int i, vector<int> path)
  27. {
  28. path.push_back(i + 1);
  29. if(path.size() < n)
  30. {
  31. bool gr[n * n];
  32. for(int j = 0; j < n * n; j++)
  33. gr[j] = graph[j];
  34. for(int j = 0; j < n; j++)
  35. gr[i * n + j] = false;
  36. gr[i * n + i] = true;
  37. vector<int> tmp = find_the_least(n, gr);
  38.  
  39. for(int j = 0; j < tmp.size(); j++)
  40. {
  41. create_string(n, gr, allPaths, tmp[j], path);
  42. }
  43. }
  44. else
  45. {
  46. allPaths->push_back(path);
  47. }
  48. }
  49.  
  50. int main()
  51. {
  52. vector<vector<int> > paths;
  53. int n, m, a, b;
  54. cin >> n >> m;
  55. bool graph[n * n];
  56. for(int i = 0; i < n * n; i++)
  57. graph[i] = false;
  58.  
  59. for(int i = 0; i < m; i++)
  60. {
  61. cin >> a >> b;
  62. graph[(a - 1) * n + (b - 1)] = true;
  63. }
  64.  
  65. vector<int> tmp = find_the_least(n, graph);
  66. vector<int> path;
  67.  
  68. for(int i = 0; i < tmp.size(); i++)
  69. create_string(n, graph, &paths, tmp[i], path);
  70.  
  71. if(paths.size() > 0)
  72. {
  73. cout << paths.size() << endl;
  74. for(int i = 0; i < paths.size(); i++)
  75. {
  76. for(int j = 0; j < n; j++)
  77. cout << paths[i][j] << " ";
  78. cout << endl;
  79. }
  80. }
  81. else
  82. {
  83. cout << "no" << endl;
  84. }
  85. return 0;
  86.  
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement