Source code for submission s656

furry.cpp

  1. #include <cstdlib>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. struct Node{
  9. Node(){
  10. visited = false;
  11. }
  12. bool visited;
  13. vector<int> edges;
  14. };
  15.  
  16. vector<Node> nodes;
  17.  
  18. bool hasZajac(int node,bool tri){
  19. if(nodes[node].visited)
  20. return false;
  21. nodes[node].visited = true;
  22. if(nodes[node].edges.size()==3){
  23. if(tri)
  24. return true;
  25. tri = true;
  26. }
  27. if(nodes[node].edges.size() > 3 ){
  28. return true;
  29. }
  30. for( int i = 0; i < nodes[node].edges.size(); i++ ){
  31. if(hasZajac(nodes[node].edges[i],tri))
  32. return true;
  33. }
  34. return false;
  35. }
  36.  
  37. int main(int argc, char * argv[]){
  38. int n,m,a,b;
  39. while(scanf("%d%d",&n,&m)==2){
  40. nodes.resize(0);
  41. nodes.resize(n);
  42. for( int i = 0; i < m; i++ ){
  43. scanf("%d%d",&a,&b);
  44. a--;
  45. b--;
  46. nodes[a].edges.push_back(b);
  47. nodes[b].edges.push_back(a);
  48. }
  49. bool zajacfound = false;
  50. for( int i = 0; i < nodes.size(); i++ ){
  51. if(!nodes[i].visited){
  52. if(hasZajac(i,false)){
  53. zajacfound = true;
  54. break;
  55. }
  56. }
  57. }
  58. printf("%s\n",zajacfound?"YES":"NO");
  59. }
  60. return 0;
  61. }
  62.