Source code for submission s801

fn.cpp

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. short * paws;
  5. bool ** graph;
  6. unsigned N;
  7.  
  8. bool isPaw(unsigned point) {
  9. if(paws[point] != -1)
  10. return (bool) paws[point];
  11. else {
  12. bool con = false;
  13. for(unsigned i = 0; i < N; i++) {
  14. if(graph[point][i] == 1) {
  15. if (con) {
  16. paws[point] = 0;
  17. return false;
  18. } else {
  19. con = true;
  20. }
  21. }
  22. }
  23.  
  24. paws[point] = 1;
  25. return true;
  26. }
  27. }
  28.  
  29. bool isBunny(unsigned point) {
  30. short paws = 0;
  31. for(unsigned i = 0; i < N; i++) {
  32. if(graph[point][i] == 1) {
  33. if(++paws > 4) {
  34. return false;
  35. }
  36. }
  37. }
  38.  
  39. if (paws == 4)
  40. return true;
  41. else
  42. return false;
  43. }
  44.  
  45. int main() {
  46. unsigned points;
  47. unsigned lines;
  48. while(cin >> points >> lines) {
  49. graph = new bool * [points];
  50. for (unsigned i = 0; i < points; i++) {
  51. graph[i] = new bool [points];
  52. for (unsigned j = 0; j < points; j++) {
  53. graph[i][j] = false;
  54. }
  55. }
  56.  
  57.  
  58. paws = new short [points];
  59. for (unsigned i = 0; i < points; i++)
  60. paws[i] = -1;
  61.  
  62. for (unsigned i = 0; i < lines; i++) {
  63. unsigned x, y;
  64. cin >> x >> y;
  65. graph[x-1][y-1] = true;
  66. graph[y-1][x-1] = true;
  67. }
  68.  
  69. N = points;
  70.  
  71. bool found = false;
  72. for (unsigned i = 0; i < N; i++) {
  73. if(isBunny(i)) {
  74. cout << "YES" << endl;
  75. found = true;
  76. break;
  77. }
  78. }
  79.  
  80. if (!found)
  81. cout << "NO" << endl;
  82.  
  83. delete [] paws;
  84.  
  85. for (unsigned i = 0; i < points; i++) {
  86. delete [] graph[i];
  87. }
  88. delete [] graph;
  89. }
  90.  
  91. return 0;
  92. }
  93.  
  94.  
  95.  
  96.