Go to diff to previous submission
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<ctype.h> #include<math.h> #include<vector> #include<set> using namespace std; #define FOR(i,a,b) for(int i=a; i<=b; i++) #define PII pair<int, int> #define MP make_pair #define PB push_back #define SIZE(s) ((int)(s).size()) #define ll long long #define MAX 10047 int N, M; vector<int> G[MAX]; int colors[MAX]; int color; void dfs(int v) { colors[v] = color; FOR(i,0, SIZE(G[v])-1) { int u = G[v][i]; if (colors[u] == 0) dfs(u); } } int V[MAX]; int st4[MAX]; vector<int> st3[MAX]; //skusime medzi dvoma vrcholmi bool skus(int v1, int v2) { // cout << v1 << " " << v2 << endl; set<int> vrchols; FOR(i,0, SIZE(G[v1])-1) if (G[v1][i] != v2) vrchols.insert( G[v1][i] ); FOR(i,0, SIZE(G[v2])-1) if (G[v2][i] != v1) vrchols.insert( G[v2][i] ); return SIZE(vrchols) >= 4; } int main() { int a, b; while(scanf("%d %d",&N, &M)== 2) { FOR(i,0,N-1) G[i].clear(); FOR(i,0,N-1) V[i] = 0; while(M--) { scanf("%d %d",&a,&b); a--; b--; G[a].PB(b); G[b].PB(a); V[a]++; V[b]++; } color = 0; FOR(i,0,N-1) colors[i] = 0; FOR(i,0,N-1) { if (colors[i] == 0) { color++; dfs(i); } } // FOR(i,0,N-1) cout << colors[i] << endl; bool ok = false; FOR(c,1,color) { st4[c] = 0; st3[c].clear(); } FOR(i,0,N-1) { if (V[i] > 3) st4[ colors[i] ]++; if (V[i] > 2) st3[ colors[i] ].PB(i); } FOR(c,1,color) { if (st4[c] >= 1) { ok = true; break; } if (SIZE(st3[c]) > 1) { FOR(i,0, SIZE( st3[c])-1) FOR(j, i+1 , SIZE(st3[c])-1) { if (skus( st3[c][i], st3[c][j])) { ok = true; break; } } } } if (ok) puts("YES"); else puts("NO"); } return 0; }
--- c5.s748.cteam079.fn.cpp.0.fn.cpp +++ c5.s753.cteam079.fn.cpp.0.fn.cpp @@ -111,6 +111,9 @@ FOR(j, i+1 , SIZE(st3[c])-1) { - if (skus( st3[c][i], st3[c][j])) ok = true; - break; + if (skus( st3[c][i], st3[c][j])) + { + ok = true; + break; + } } }