Go to diff to previous submission
#include <iostream> #include <vector> #include <cstdio> #include <cmath> #include <set> #include <map> #include <string> using namespace std; vector< vector<int> > G; bool marked[1000000]; bool ok = false; vector<int> good; int visited; void tam(int v) { visited++; marked[v] = true; for(int i=0; i<G[v].size(); i++) { int u = G[v][i]; if(marked[u]) continue; tam(u); } } void zpet(int v) { visited++; marked[v] = false; for(int i=0; i<G[v].size(); i++) { int u = G[v][i]; if(!marked[u]) continue; zpet(u); } } void dfs(int v) { if(G[v].size() >= 4) ok = true; else if(G[v].size() == 3) { //printf("test %d\n", v); for(int i=0; !ok && i<good.size(); i++) { int u = good[i]; //printf("%d %d\n", v, u); set<int> s; for(int j=0; j<G[v].size(); j++) { if(G[v][j] != u) s.insert(G[v][j]); } for(int j=0; j<G[u].size(); j++) { if(G[u][j] != v) s.insert(G[u][j]); } if(s.size() >= 4) { ok = true; } } good.push_back(v); } if(ok) return; visited++; marked[v] = true; for(int i=0; !ok && i< G[v].size(); i++) { int u = G[v][i]; if(marked[u]) continue; dfs(u); } } int main() { int N, M; while(scanf("%d %d", &N, &M) == 2) { G = vector< vector<int> >(N); for(int i=0; i<N; i++) { G[i] = vector<int>(); marked[i] = false; } for(int i=0; i<M; i++) { int x, y; scanf("%d %d", &x, &y); --x; --y; G[x].push_back(y); G[y].push_back(x); } ok = false; for(int i=0; !ok && i<N; i++) { visited = 0; good = vector<int>(); if(!marked[i]) { visited = 0; tam(i); //printf("tam from %d visited %d\n", i, visited); if(visited <= 4) { //printf("smula from %d visited %d\n", i, visited); continue; } visited = 0; zpet(i); //printf("zpet from %d visited %d\n", i, visited); visited = 0; dfs(i); //printf("dfs from %d visited %d\n", i, visited); } } if(!ok) puts("NO"); else puts("YES"); } return 0; }
--- c5.s819.cteam036.fn.cpp.0.fn.cpp +++ c5.s1029.cteam036.fn.cpp.0.fn.cpp @@ -12,7 +12,35 @@ bool marked[1000000]; bool ok = false; -int good; +vector<int> good; int visited; +void tam(int v) +{ + visited++; + marked[v] = true; + + for(int i=0; i<G[v].size(); i++) + { + int u = G[v][i]; + if(marked[u]) + continue; + tam(u); + } +} + +void zpet(int v) +{ + visited++; + marked[v] = false; + + for(int i=0; i<G[v].size(); i++) + { + int u = G[v][i]; + if(!marked[u]) + continue; + zpet(u); + } +} + void dfs(int v) { @@ -20,10 +48,38 @@ ok = true; else if(G[v].size() == 3) - good++; + { + //printf("test %d\n", v); + for(int i=0; !ok && i<good.size(); i++) + { + int u = good[i]; + + //printf("%d %d\n", v, u); + + set<int> s; + for(int j=0; j<G[v].size(); j++) + { + if(G[v][j] != u) + s.insert(G[v][j]); + } + for(int j=0; j<G[u].size(); j++) + { + if(G[u][j] != v) + s.insert(G[u][j]); + } + if(s.size() >= 4) + { + ok = true; + } + } + good.push_back(v); + } + + if(ok) + return; visited++; marked[v] = true; - for(int i=0; i<G[v].size(); i++) + for(int i=0; !ok && i< G[v].size(); i++) { int u = G[v][i]; @@ -58,9 +114,22 @@ { visited = 0; - good = 0; + good = vector<int>(); if(!marked[i]) + { + visited = 0; + tam(i); + //printf("tam from %d visited %d\n", i, visited); + if(visited <= 4) + { + //printf("smula from %d visited %d\n", i, visited); + continue; + } + visited = 0; + zpet(i); + //printf("zpet from %d visited %d\n", i, visited); + visited = 0; dfs(i); - if(good >= 2 && visited >= 5) - ok = true; + //printf("dfs from %d visited %d\n", i, visited); + } } if(!ok)