# 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