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(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; while (scanf("%d %d\n",&N,&M) > 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); 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 <= 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; }
--- 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; }