Source code for submission s636

fn.cpp

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. int N,M;
  6. while(cin >> N >> M) {
  7. vector< vector<int> > G(N);
  8. vector<int> D(N,0);
  9. vector<int> d3;
  10. for(int i =0; i < M; i++){
  11. int a,b;
  12. cin >> a >> b;
  13. G[--a].push_back(--b);
  14. G[b].push_back(a);
  15. D[a]++, D[b]++;}
  16. int maxD =0;
  17. for(int i =0; i < N; i++) {
  18. if(D[i] == 3) d3.push_back(i);
  19. maxD =max(maxD,D[i]);}
  20. if(maxD > 3 || d3.size() > 42) {cout << "YES\n"; continue;}
  21. if(maxD < 3) {cout << "NO\n"; continue;}
  22.  
  23. vector<int> comp(N,-1);
  24. int c =0;
  25. queue<int> q;
  26. for(int k =0; k < N; k++) if(comp[k] == -1) {
  27. q.push(k);
  28. comp[k] =c;
  29. while(!q.empty()) {
  30. int a =q.front();
  31. for(int i =0; i < G[a].size(); i++) if(comp[G[a][i]] == -1) {
  32. comp[G[a][i]] =c;
  33. q.push(G[a][i]);}
  34. q.pop();}
  35. c++;}
  36.  
  37. bool ok =false;
  38. for(int i =0; i < d3.size(); i++) for(int j =0; j < d3.size(); j++) if(comp[d3[i]] == comp[d3[j]]) {
  39. int com =0, a =d3[i], b =d3[j];
  40. for(int k =0; k < 3; k++) for(int l =0; l < 3; l++) if(G[a][k] == G[b][l]) com++;
  41. bool hr =false;
  42. for(int k =0; k < 3; k++) if(G[a][k] == b) hr =true;
  43. if(hr && com == 0) ok =true;
  44. if(!hr && com <= 1) ok =true;}
  45. if(ok) cout << "YES\n";
  46. else cout << "NO\n";}
  47. return 0;}
  48.