Go to diff to previous submission
#include <iostream> #include <cctype> #include <cmath> #include <complex> #include <cstdio> #include <string> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <utility> #include <vector> using namespace std; #define DEBUG(x) cout << ">>> " #x << " : " << x << endl; map<int,vector<int> > neighbours; map<int,bool> visited; map<int,bool> open; int dsp( int v, int p ) { if( neighbours[v].size() == 1 && neighbours[v][0] == p ) return 1; visited[v] = true; open[v] = true; int sum = 0; for( size_t i = 0; i < neighbours[v].size(); i++ ) { if( open[neighbours[v][i]] ) { sum++; } else { sum += dsp( neighbours[v][i], v ); } } open[v] = false; return sum; } int main() { int n,m; while( scanf("%d %d", &n, &m) == 2 ) { neighbours.clear(); visited.clear(); open.clear(); for( int i = 0; i < m; i++ ) { int u,v; scanf( "%d %d", &u, &v ); neighbours[u].push_back(v); neighbours[v].push_back(u); } bool found = false; for( int i = 0; i < m; i++ ) { if( visited[i] ) continue; if( dsp( i, -1 ) >= 4 ) found = true; } if( found ) { printf( "YES\n" ); } else { printf( "NO\n" ); } } return 0; }
--- c5.s687.cteam018.fn.cpp.0.fn.cpp +++ c5.s891.cteam018.fn.cpp.0.fn.cpp @@ -18,13 +18,32 @@ #define DEBUG(x) cout << ">>> " #x << " : " << x << endl; +map<int,vector<int> > neighbours; +map<int,bool> visited; +map<int,bool> open; + +int dsp( int v, int p ) { + if( neighbours[v].size() == 1 && neighbours[v][0] == p ) return 1; + visited[v] = true; + + open[v] = true; + int sum = 0; + for( size_t i = 0; i < neighbours[v].size(); i++ ) { + if( open[neighbours[v][i]] ) { + sum++; + } else { + sum += dsp( neighbours[v][i], v ); + } + } + open[v] = false; + + return sum; +} + int main() { int n,m; while( scanf("%d %d", &n, &m) == 2 ) { - map<int,int> neighbours; - bool found = false; - - for( int i = 0; i < n; i++ ) { - neighbours[i] = 0; - } + neighbours.clear(); + visited.clear(); + open.clear(); for( int i = 0; i < m; i++ ) { @@ -32,6 +51,12 @@ scanf( "%d %d", &u, &v ); - if( ++neighbours[u] >= 4 ) { found = true; } - if( ++neighbours[v] >= 4 ) { found = true; } + neighbours[u].push_back(v); + neighbours[v].push_back(u); + } + + bool found = false; + for( int i = 0; i < m; i++ ) { + if( visited[i] ) continue; + if( dsp( i, -1 ) >= 4 ) found = true; }