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; int good; void dfs(int v) { if(G[v].size() >= 4) ok = true; else if(G[v].size() == 3) good++; if(good == 2) ok = true; if(ok) return; 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++) { good = 0; if(!marked[i]) dfs(i); } if(!ok) puts("NO"); else puts("YES"); } return 0; }
--- c5.s761.cteam036.fn.cpp.0.fn.cpp +++ c5.s798.cteam036.fn.cpp.0.fn.cpp @@ -12,6 +12,7 @@ bool marked[1000000]; bool ok = false; +int good; -void dfs(int v, int good) +void dfs(int v) { if(G[v].size() >= 4) @@ -33,5 +34,5 @@ if(marked[u]) continue; - dfs(u,good); + dfs(u); } } @@ -60,6 +61,7 @@ for(int i=0; !ok && i<N; i++) { + good = 0; if(!marked[i]) - dfs(i,0); + dfs(i); } if(!ok)