Source code for submission s1000

fn.cpp

  1. //
  2. // File:   fs.cc
  3. // Author: cteam008
  4. //
  5. // Created on October 19, 2013, 10:50 AM
  6. //
  7.  
  8. #include <stdlib.h>
  9. #include <stdio.h>
  10. #include <iostream>
  11. #include <vector>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16.  
  17. //
  18. //
  19. //
  20. int main(int argc, char** argv) {
  21.     int n, m, x, y, z;
  22.     vector<int> deg3;
  23.     bool isDeg4, same;
  24.     while (cin >> n >> m) {
  25.         vector<int> edges[n+1];
  26.         int deg[n+1];
  27.         for (int i = 0; i <= n; i++) {
  28.             deg[i] = 0;
  29.         }
  30.         deg3.clear();
  31.         isDeg4 = false;
  32.         for (int i = 0; i < m; i++) {
  33.             cin >> x >> y;
  34.             deg[x]++;
  35.             if (deg[x] >= 4) {
  36.                 isDeg4 = true;
  37.             } else {
  38.                 if (deg[x] == 3) {
  39.                     deg3.push_back(x);
  40.                 }
  41.                 edges[x].push_back(y);
  42.             }
  43.             deg[y]++;
  44.             if (deg[y] >= 4) {
  45.                 isDeg4 = true;
  46.             } else {
  47.                 if (deg[y] == 3) {
  48.                     deg3.push_back(y);
  49.                 }
  50.                 edges[y].push_back(x);
  51.             }
  52.         }
  53.         if (isDeg4) {
  54.             cout << "YES" << endl;
  55.             continue;
  56.         }
  57.         if (deg3.size() < 2) {
  58.             cout << "NO" << endl;
  59.             continue;
  60.         }
  61.         for (int i = 1; i < deg3.size(); i++) {
  62.             vector<bool> used(n+1, false);
  63.             x = deg3[i];
  64.             used[x]=true;
  65.             queue<int> fifo;
  66.             for (int j = 0; j < 3; j++) {
  67.                 y =edges[x][j];
  68.                 if (deg[y] == 3) {
  69.                     same = false;
  70.                     for (int h = 0; h < 3; h++) {
  71.                         for (int k = 0; k < 3; k++) {
  72.                             if (edges[x][h]==edges[y][k]) {
  73.                                 same = true;
  74.                                 break;
  75.                             }
  76.                         }
  77.                         if (same) break;
  78.                     }
  79.                     if (!same) {
  80.                         isDeg4 = true;
  81.                         break;
  82.                     }
  83.                     used[y]=true;
  84.                     fifo.push(y);
  85.                 } else if (deg[y] == 2) {
  86.                     used[y]=true;
  87.                     y = (edges[y][0] == x) ? edges[y][1] : edges[y][0];
  88.                     same = false;
  89.                     for (int h = 0; h < 3; h++) {
  90.                         for (int k = 0; k < 3; k++) {
  91.                             if (edges[x][h]==edges[y][k]) {
  92.                                 same = true;
  93.                                 break;
  94.                             }
  95.                         }
  96.                         if (same) break;
  97.                     }
  98.                     if (!same) {
  99.                         isDeg4 = true;
  100.                         break;
  101.                     }
  102.                     used[y]=true;
  103.                     fifo.push(y);
  104.                 }
  105.             }
  106.             if (isDeg4) {
  107.                 break;
  108.             }
  109.             while (!fifo.empty()) {
  110.                 x = fifo.front();
  111.                 fifo.pop();
  112.                 for (int j = 0; j < deg[x]; j++) {
  113.                     y = edges[x][j];
  114.                     if (!used[y]) {
  115.                         if (deg[y] == 3) {
  116.                             isDeg4 = true;
  117.                             break;
  118.                         }
  119.                         fifo.push(y);
  120.                     }
  121.  
  122.                 }
  123.                 if (isDeg4) {
  124.                     break;
  125.                 }
  126.             }
  127.  
  128.         }
  129.         if (isDeg4) {
  130.             cout << "YES" << endl;
  131.  
  132.         } else {
  133.             cout << "NO" << endl;
  134.         }
  135.  
  136.  
  137.     }
  138.     return (EXIT_SUCCESS);
  139. }
  140.