Advertisement
Guest User

Untitled

a guest
Oct 21st, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<vector<int> > g, gr;
  6. vector<char> used;
  7. vector<int> order, component;
  8.  
  9. void dfs1(int v) {
  10.     used[v] = true;
  11.     for (size_t i = 0; i < g[v].size(); ++i)
  12.         if (!used[g[v][i]])
  13.             dfs1(g[v][i]);
  14.     order.push_back(v);
  15. }
  16.  
  17. void dfs2(int v) {
  18.     used[v] = true;
  19.     component.push_back(v);
  20.     for (size_t i = 0; i < gr[v].size(); ++i)
  21.         if (!used[gr[v][i]])
  22.             dfs2(gr[v][i]);
  23. }
  24.  
  25. int main() {
  26.     int n, m, a, b, index_a, index_b, indexNot_a, indexNot_b;
  27.     pair<int, int> kek;
  28.     cin >> n >> m;
  29.     n = n * 2;
  30.     g.resize(n);
  31.     gr.resize(n);
  32.    
  33.     vector<pair<int,int>> allVertexNotVertex;
  34.     for (int i = 0; i < n; i+=2) {
  35.         kek.first = i;
  36.         kek.second = i + 1;
  37.         allVertexNotVertex.push_back(kek);
  38.     }
  39.  
  40.     for (int i = 0; i < m; i++) {
  41.         cin >> a >> b;
  42.         if (a < 0) {
  43.             index_a = (-a * 2) - 1;
  44.             indexNot_a = index_a - 1;
  45.         } else {
  46.             index_a = (a * 2) - 2;
  47.             indexNot_a = index_a + 1;
  48.         }
  49.         if (b < 0) {
  50.             index_b = (-b * 2) - 1;
  51.             indexNot_b = index_b - 1;
  52.         } else {
  53.             index_b = (b * 2) - 2;
  54.             indexNot_b = index_b + 1;
  55.         }
  56.         g[indexNot_a].push_back(index_b);
  57.         gr[index_b].push_back(indexNot_a);
  58.         g[indexNot_b].push_back(index_a);
  59.         gr[index_a].push_back(indexNot_b);
  60.     }
  61.  
  62.     used.assign(n, false);
  63.     for (int i = 0; i < n; ++i)
  64.         if (!used[i])
  65.             dfs1(i);
  66.     used.assign(n, false);
  67.     for (int i = 0; i < n; ++i) {
  68.         int v = order[n - 1 - i];
  69.         if (!used[v]) {
  70.             dfs2(v);
  71.             sort(component.begin(), component.end());
  72.             for (int j = 0; j < component.size() - 1; j++) {
  73.                 if (component[j + 1] - component[j] == 1) {
  74.                     kek.first = component[j];
  75.                     kek.second = component[j + 1];
  76.                     auto result1 = find(allVertexNotVertex.begin(), allVertexNotVertex.end(), kek);
  77.                     if (result1 != allVertexNotVertex.end()) {
  78.                         cout << "YES";
  79.                         return 0;
  80.                     }
  81.                     else
  82.                         continue;
  83.                 }
  84.             }
  85.             component.clear();
  86.         }
  87.     }
  88.     cout << "NO";
  89.  
  90.     /*
  91.     vector<bool> core(2*n, 0);
  92.     vector<vector<bool>> graph(2*n, core);
  93.  
  94.     for (int i = 0; i < m; i++) {
  95.         cin >> a >> b;
  96.         if (a < 0) {
  97.             index_a = (-a * 2) - 1;
  98.             indexNot_a = index_a - 1;
  99.         }
  100.         else {
  101.             index_a = (a * 2) - 2;
  102.             indexNot_a = index_a + 1;
  103.         }
  104.         if (b < 0) {
  105.             index_b = (-b * 2) - 1;
  106.             indexNot_b = index_b - 1;
  107.         }
  108.         else {
  109.             index_b = (b * 2) - 2;
  110.             indexNot_b = index_b + 1;
  111.         }
  112.         graph[indexNot_a][index_b] = 1;
  113.         graph[indexNot_b][index_a] = 1;
  114.     }
  115.  
  116.     for (int i = 0; i < 2*n; i++) {
  117.         for (int j = 0; j < 2*n; j++) {
  118.             cout << graph[i][j] << " ";
  119.         }
  120.         cout << endl;
  121.     }
  122.     */
  123.  
  124.     return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement