Source code for submission s955

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.    {
  52.     scanf("%d %d\n",&x,&y); 
  53.  
  54.     arr[x].push_back(y);
  55.     arr[y].push_back(x);
  56.     if (arr[x].size() >= 4 || arr[y].size() >= 4)
  57.             {  ans = true; }
  58.     }  
  59.  
  60.     if (!ans)
  61.     {
  62.         int cc = 1;
  63.         for (int i = 1; i <= N; ++i)
  64.         {
  65.             if (comp[i] == -1)
  66.                 go(i, cc++);
  67.         }
  68.  
  69.         kom.resize(cc);
  70. //        cout << "kom " << cc << endl;
  71.         for (int i = 1; i <= N; ++i)
  72.         {
  73.             if (arr[i].size() > 2)
  74.                 kom[comp[i]].push_back(i);
  75.         }
  76.  
  77.         for (int i = 0; !ans && i < kom.size(); ++i)
  78.         {
  79.             vector<int>& tmp = kom[i];
  80.  
  81.             for (int j = 0; !ans && j < tmp.size(); ++j)
  82.                 for (int k = j+1; !ans && k < tmp.size(); ++k)
  83.                    if (intersect(arr[tmp[j]], arr[tmp[k]]))
  84.                      ans = true; 
  85.         }
  86.     }
  87.  
  88.     if (ans)
  89.         printf("YES\n");
  90.     else
  91.         printf("NO\n");
  92. }
  93.  
  94. return 0;
  95. }
  96.  

Diff to submission s933

fn.cpp

--- c5.s933.cteam078.fn.cpp.0.fn.cpp
+++ c5.s955.cteam078.fn.cpp.0.fn.cpp
@@ -61,5 +61,5 @@
     {
         int cc = 1;
-        for (int i = 1; i <= M; ++i)
+        for (int i = 1; i <= N; ++i)
         {
             if (comp[i] == -1)
@@ -68,5 +68,5 @@
 
         kom.resize(cc);
-    
+//        cout << "kom " << cc << endl;
         for (int i = 1; i <= N; ++i)
         {