SHARE
TWEET

Untitled

a guest Dec 14th, 2019 74 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top