Go to diff to previous submission
#include <cstdio> #include <vector> #include <iostream> #include <string> #include <algorithm> #include <cstring> #include <set> #include <vector> 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(int a, int b) { int end = 6; set<int> s; s.insert(a); s.insert(b); for (int i = 0; i < arr[a].size(); ++i) { s.insert(arr[a][i]); if (arr[a][i] == b) ++end; } for (int i = 0; i < arr[b].size(); ++i) { s.insert(arr[b][i]); if (arr[b][i] == a) ++end; } // cout << end << endl; return s.size() >= end; } int main() { int N,M,x,y,i; while (scanf("%d %d\n",&N,&M) > 0) { bool ans = false; arr.clear(); arr.resize(N+1); comp.clear(); comp.resize(N+1, -1); kom.clear(); for(i=1;i<=M;i++) { scanf("%d %d\n",&x,&y); arr[x].push_back(y); arr[y].push_back(x); if (arr[x].size() >= 4 || arr[y].size() >= 4) { ans = true; } } if (!ans) { int cc = 1; for (int i = 1; i <= N; ++i) { if (comp[i] == -1) go(i, cc++); } kom.resize(cc); // cout << "kom " << cc << endl; for (int i = 1; i <= N; ++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(tmp[j], tmp[k])) { ans = true; //cout << "match " << tmp[j] << " " << tmp[k] << endl; } } } if (ans) printf("YES\n"); else printf("NO\n"); } return 0; }
--- c5.s996.cteam078.fn.cpp.0.fn.cpp +++ c5.s1068.cteam078.fn.cpp.0.fn.cpp @@ -24,4 +24,5 @@ bool intersect(int a, int b) { + int end = 6; set<int> s; s.insert(a); @@ -27,11 +28,20 @@ s.insert(a); s.insert(b); + for (int i = 0; i < arr[a].size(); ++i) + { s.insert(arr[a][i]); + if (arr[a][i] == b) + ++end; + } for (int i = 0; i < arr[b].size(); ++i) + { s.insert(arr[b][i]); - - return s.size() >= 6; + if (arr[b][i] == a) + ++end; + } +// cout << end << endl; + return s.size() >= end; } @@ -87,5 +97,5 @@ { ans = true; - //cout << "match " << tmp[j] << " " << tmp[k] << endl; + //cout << "match " << tmp[j] << " " << tmp[k] << endl; } }