Source code for submission s996

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(int a, int b)
  25. {
  26.     set<int> s;
  27.     s.insert(a);
  28.     s.insert(b);
  29.     for (int i = 0; i < arr[a].size(); ++i)
  30.         s.insert(arr[a][i]);
  31.  
  32.     for (int i = 0; i < arr[b].size(); ++i)
  33.         s.insert(arr[b][i]);
  34.  
  35.     return s.size() >= 6;
  36. }
  37.  
  38. int main()
  39. {
  40. int N,M,x,y,i;
  41.  
  42.  
  43.  
  44. while (scanf("%d %d\n",&N,&M) > 0)
  45. {
  46.     bool ans = false;
  47.     arr.clear();
  48.     arr.resize(N+1);
  49.     comp.clear();
  50.     comp.resize(N+1, -1);
  51.     kom.clear();
  52.  
  53.    for(i=1;i<=M;i++)
  54.    {
  55.     scanf("%d %d\n",&x,&y); 
  56.  
  57.     arr[x].push_back(y);
  58.     arr[y].push_back(x);
  59.     if (arr[x].size() >= 4 || arr[y].size() >= 4)
  60.             {  ans = true; }
  61.     }  
  62.  
  63.     if (!ans)
  64.     {
  65.         int cc = 1;
  66.         for (int i = 1; i <= N; ++i)
  67.         {
  68.             if (comp[i] == -1)
  69.                 go(i, cc++);
  70.         }
  71.  
  72.         kom.resize(cc);
  73. //        cout << "kom " << cc << endl;
  74.         for (int i = 1; i <= N; ++i)
  75.         {
  76.             if (arr[i].size() > 2)
  77.                 kom[comp[i]].push_back(i);
  78.         }
  79.  
  80.         for (int i = 0; !ans && i < kom.size(); ++i)
  81.         {
  82.             vector<int>& tmp = kom[i];
  83.  
  84.             for (int j = 0; !ans && j < tmp.size(); ++j)
  85.                 for (int k = j+1; !ans && k < tmp.size(); ++k)
  86.                    if (intersect(tmp[j], tmp[k]))
  87.                    {
  88.                      ans = true; 
  89.                    //cout << "match " << tmp[j] << " " << tmp[k] << endl;
  90.                     }
  91.         }
  92.     }
  93.  
  94.     if (ans)
  95.         printf("YES\n");
  96.     else
  97.         printf("NO\n");
  98. }
  99.  
  100. return 0;
  101. }
  102.  

Diff to submission s971

fn.cpp

--- c5.s971.cteam078.fn.cpp.0.fn.cpp
+++ c5.s996.cteam078.fn.cpp.0.fn.cpp
@@ -49,4 +49,5 @@
     comp.clear();
     comp.resize(N+1, -1);
+    kom.clear();
 
    for(i=1;i<=M;i++)