Source code for submission s790

fn.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. ///////////////////////////////////////////////////////////////////////////
  29.  
  30. const int MAX = 10007;
  31. int N, M;
  32. vector<int> graph[MAX];
  33. int visited[MAX];
  34.  
  35. bool go(int node)
  36. {
  37. queue<int> manage;
  38. manage.push(node);
  39. visited[node] = true;
  40.  
  41. int sum = 0, root = node;
  42. while (!manage.empty())
  43. {
  44. node = manage.front();
  45. manage.pop();
  46.  
  47. int found = 0;
  48. REP(i, graph[node].size())
  49. {
  50. int next = graph[node][i];
  51. if (!visited[next])
  52. {
  53. manage.push(next);
  54. visited[next] = true;
  55. found += 1;
  56. }
  57. }
  58. if (!found || (node==root && found==1)) sum += 1;
  59. }
  60. return sum >= 4;
  61. }
  62.  
  63. int main()
  64. {
  65. while (scanf("%d%d", &N, &M) == 2)
  66. {
  67. REP(i, N) graph[i].clear();
  68. REP(i, M)
  69. {
  70. int a, b;
  71. scanf("%d%d", &a, &b);
  72. --a, --b;
  73. graph[a].push_back(b);
  74. graph[b].push_back(a);
  75. }
  76. memset(visited, 0, sizeof(visited));
  77. bool ok = false;
  78. REP(i, N)
  79. if (!visited[i])
  80. ok = ok || go(i);
  81. if (ok) printf("YES\n");
  82. else printf("NO\n");
  83. }
  84.  
  85. return 0;
  86. }