Source code for submission s928

Go to diff to previous submission

fn.cpp

  1. #include <cstdio>
  2. #include <vector>
  3. #include <iostream>
  4. #include <string>
  5. #include <algorithm>
  6. #include <cstring>
  7. #include <set>
  8. #include <vector>
  9.  
  10. using namespace std;
  11.  
  12. vector<vector<int> > arr;
  13. vector<vector<int> > kom;
  14. vector<int> comp;
  15.  
  16. void go(int a, int c)
  17. {
  18. comp[a] = c;
  19. for (int i = 0; i < arr[a].size(); ++i)
  20. if (comp[arr[a][i]] == -1)
  21. go(arr[a][i], c);
  22. }
  23.  
  24. bool intersect(vector<int>& a, vector<int>& b)
  25. {
  26. set<int> s;
  27. for (int i = 0; i < a.size(); ++i)
  28. s.insert(a[i]);
  29.  
  30. for (int i = 0; i < b.size(); ++i)
  31. s.insert(b[i]);
  32.  
  33. return s.size() >= 4;
  34. }
  35.  
  36. int main()
  37. {
  38. int N,M,x,y,i;
  39.  
  40.  
  41.  
  42. while (scanf("%d %d\n",&N,&M) > 0)
  43. {
  44. bool ans = false;
  45. arr.clear();
  46. arr.resize(N+1);
  47. comp.clear();
  48. comp.resize(N+1, -1);
  49.  
  50. for(i=1;i<=M;i++)
  51. { scanf("%d %d\n",&x,&y);
  52.  
  53. arr[x].push_back(y);
  54. arr[y].push_back(x);
  55. if (arr[x].size() >= 4 || arr[y].size() >= 4)
  56. { ans = true; }
  57. }
  58.  
  59. if (!ans)
  60. {
  61. int cc = 1;
  62. for (int i = 1; i <= M; ++i)
  63. {
  64. if (comp[i] == -1)
  65. go(i, cc++);
  66. }
  67.  
  68. kom.resize(cc);
  69.  
  70. for (int i = 1; i <= M; ++i)
  71. {
  72. if (arr[i].size() > 2)
  73. kom[comp[i]].push_back(i);
  74. }
  75.  
  76. for (int i = 0; !ans && i < kom.size(); ++i)
  77. {
  78. vector<int>& tmp = kom[i];
  79. for (int j = 0; !ans && j < tmp.size(); ++j)
  80. for (int k = j+1; !ans && k < tmp.size(); ++k)
  81. if (intersect(arr[tmp[j]], arr[tmp[k]]))
  82. ans = true;
  83. }
  84. }
  85.  
  86. if (ans)
  87. printf("YES\n");
  88. else
  89. printf("NO\n");
  90. }
  91.  
  92. return 0;
  93. }
  94.  

Diff to submission s822

fn.cpp

--- c5.s822.cteam078.fn.cpp.0.fn.cpp
+++ c5.s928.cteam078.fn.cpp.0.fn.cpp
@@ -10,20 +10,84 @@
 using namespace std;
 
+vector<vector<int> > arr;
+vector<vector<int> > kom;
+vector<int> comp;
+
+void go(int a, int c)
+{
+    comp[a] = c;
+    for (int i = 0; i < arr[a].size(); ++i)
+        if (comp[arr[a][i]] == -1)
+            go(arr[a][i], c);
+}
+
+bool intersect(vector<int>& a, vector<int>& b)
+{
+    set<int> s;
+    for (int i = 0; i < a.size(); ++i)
+        s.insert(a[i]);
+
+    for (int i = 0; i < b.size(); ++i)
+        s.insert(b[i]);
+
+    return s.size() >= 4;
+}
+
 int main()
 {
 int N,M,x,y,i;
-int p[10001];
+
+
 
 while (scanf("%d %d\n",&N,&M) > 0)
 {
- for(i=0;i<=10000;i++) p[i]=0;
+    bool ans = false;
+    arr.clear();
+    arr.resize(N+1);
+    comp.clear();
+    comp.resize(N+1, -1);
+
  for(i=1;i<=M;i++)
    { scanf("%d %d\n",&x,&y); 
-     p[x]++;
-     p[y]++;
-     if (p[x]==4 || p[y] == 4) break;
+
+    arr[x].push_back(y);
+    arr[y].push_back(x);
+        if (arr[x].size() >= 4 || arr[y].size() >= 4)
+            {  ans = true; }
     }  
-   if (p[x]==4 || p[y] == 4) printf("YES\n"); else printf("NO\n");
+
+    if (!ans)
+    {
+        int cc = 1;
+        for (int i = 1; i <= M; ++i)
+        {
+            if (comp[i] == -1)
+                go(i, cc++);
+        }
+
+        kom.resize(cc);
+    
+        for (int i = 1; i <= M; ++i)
+        {
+            if (arr[i].size() > 2)
+                kom[comp[i]].push_back(i);
+        }
+
+        for (int i = 0; !ans && i < kom.size(); ++i)
+        {
+            vector<int>& tmp = kom[i];
+            for (int j = 0; !ans && j < tmp.size(); ++j)
+                for (int k = j+1; !ans && k < tmp.size(); ++k)
+                   if (intersect(arr[tmp[j]], arr[tmp[k]]))
+                     ans = true; 
+        }
+    }
+
+    if (ans)
+        printf("YES\n");
+    else
+        printf("NO\n");
 }
+
 return 0;
 }