Guest User

Untitled

a guest
Dec 14th, 2019
96
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <iostream>
  3. #include <queue>
  4. #include <math.h>
  5.  
  6. class MatrixGraph {
  7.  
  8. public:
  9.  
  10. std::vector<std::vector<int>> data;
  11.  
  12. MatrixGraph(int N);
  13.  
  14. ~MatrixGraph() {};
  15.  
  16. void AddEdge(int from, int to);
  17.  
  18. };
  19.  
  20.  
  21. MatrixGraph::MatrixGraph(int N) {
  22. std::vector<bool> tmp;
  23. for (int i = 0; i < N; i++) {
  24. std::vector<int> tmp;
  25. data.push_back(tmp);
  26. }
  27.  
  28. }
  29.  
  30.  
  31. void MatrixGraph::AddEdge(int from, int to) {
  32. data.at(from).push_back(to);
  33. data.at(to).push_back(from);
  34. }
  35.  
  36.  
  37. int main()
  38. {
  39. int N, M;
  40. std::cin >> N >> M;
  41. int res = N + 1;
  42. MatrixGraph graph(N);
  43.  
  44. for (int i = 0; i < M; i++) {
  45. int from, to;
  46. std::cin >> from >> to;
  47. graph.AddEdge(from, to);
  48. }
  49.  
  50. for (int j = 0; j < N; j++) {
  51. std::queue<int> q;
  52. q.push(j);
  53. std::vector<bool> used(N);
  54. std::vector<int> d(N), p(N);
  55. d[j] = 0;
  56. used[j] = true;
  57. p[j] = -1;
  58. while (!q.empty()) {
  59. int v = q.front();
  60. q.pop();
  61. for (int i = 0; i < graph.data[v].size(); i++) {
  62. int to = graph.data[v][i];
  63. if (!used[to]) {
  64. used[to] = true;
  65. q.push(to);
  66. d[to] = d[v] + 1;
  67. p[to] = v;
  68. }
  69. else {
  70. int tmp = d[v] + d[to] + 1;
  71. if (tmp < res && to != p[v]) res = tmp;
  72. }
  73. }
  74. }
  75. }
  76. if (res == N + 1)
  77. res = -1;
  78.  
  79. std::cout << res;
  80. return 0;
  81. }
RAW Paste Data