Guest User

Untitled

a guest
Dec 14th, 2019
81
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. private:
  9.  
  10. std::vector<std::vector<bool>> data;
  11.  
  12. public:
  13.  
  14. MatrixGraph(size_t N);
  15.  
  16. ~MatrixGraph() {};
  17.  
  18. void AddEdge(size_t from, size_t to);
  19.  
  20. std::vector<size_t> GetVertices(size_t vertice);
  21.  
  22. };
  23.  
  24.  
  25. MatrixGraph::MatrixGraph(size_t N) {
  26. std::vector<bool> tmp;
  27. for (size_t i = 0; i < N; i++) {
  28. std::vector<bool> tmp;
  29. for (size_t j = 0; j < N; j++)
  30. tmp.push_back(false);
  31. data.push_back(tmp);
  32. }
  33.  
  34. }
  35.  
  36.  
  37. void MatrixGraph::AddEdge(size_t from, size_t to) {
  38. data.at(from).at(to) = true;
  39. data.at(to).at(from) = true;
  40. }
  41.  
  42.  
  43. std::vector<size_t> MatrixGraph::GetVertices(size_t from) {
  44. std::vector<size_t> res;
  45. for (size_t to = 0; to < data.size(); to++) {
  46. if (data.at(from).at(to) == true)
  47. res.push_back(to);
  48. }
  49. return res;
  50. }
  51.  
  52.  
  53. bool in(size_t digit, std::vector<size_t> vec) {
  54. for (size_t i = 0; i < vec.size(); i++) {
  55. if (digit == vec[i]) return true;
  56. }
  57. return false;
  58. }
  59.  
  60. int main()
  61. {
  62. size_t N, M;
  63. std::cin >> N >> M;
  64. int res = N + 1;
  65. MatrixGraph graph(N);
  66.  
  67. for (size_t i = 0; i < M; i++) {
  68. size_t from, to;
  69. std::cin >> from >> to;
  70. graph.AddEdge(from, to);
  71. }
  72.  
  73.  
  74. std::vector<size_t> A, B;
  75. std::vector<bool> used(N);
  76. for (size_t j = 0; j < N; j++) {
  77. if (used[j]) continue;
  78. std::queue<int> q;
  79. q.push(j);
  80. used[j] = true;
  81. A.push_back(j);
  82. bool sign;
  83. while (!q.empty()) {
  84. int v = q.front();
  85. q.pop();
  86.  
  87. if (in(v, A)) sign = true;
  88. else sign = false;
  89.  
  90. for (size_t i = 0; i < graph.GetVertices(v).size(); i++) {
  91. int to = graph.GetVertices(v)[i];
  92. if (!used[to]) {
  93. used[to] = true;
  94. q.push(to);
  95. if (sign == true) {
  96. B.push_back(to);
  97. }
  98. else {
  99. A.push_back(to);
  100. }
  101. }
  102. else if (in(to, A) && in(v, A) || in(to, B) && in(v, B)) {
  103. std::cout << "NO";
  104. return 0;
  105. }
  106. }
  107. }
  108. }
  109. std::cout << "YES";
  110. return 0;
  111. }
RAW Paste Data