Go to diff to previous submission
#include <algorithm> #include <cmath> #include<cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define REP(i,n) for ( int i = 0; i < (n); i++) #define FOR(i,a,b) for ( int i = (a); i <= (b); i++ ) #define FORD(i,a,b) for ( int i = (a); i>= (b); i-- ) #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl; queue<int> q; bool bunny; int grade[10024]; bool visited [10024]; int sib[10024][10024]; int sibCnt[10024]; int p1, p2, points, lines,res; /* void dfs (int node, bool first) { int cnt = 0; if (visited[node]) return; if (first && sibCnt[node]==1) res++; bool found = false; visited[node] = true; //DEBUG(sibCnt[node]); for (int i = 0; i < sibCnt[node]; i++) { if (!visited[sib[node][i]]) { if (first) cnt++; //cout << "Node " << sib[node][i] << endl; dfs (sib[node][i],false); found = true; } } if (first && cnt==1) res++; if (!found) res++; } */ void bfs (int node) { bool found = false; if (visited[node]) return; q.push(node); if (sibCnt[node] == 1) res++; while(!q.empty()) { found = false; node = q.front(); q.pop(); visited[node] = true; REP(i, sibCnt[node]) { if (!visited[sib[node][i]]) { q.push(sib[node][i]); found = true; } } if (!found) res++; } //DEBUG(res); } int main() { while(scanf("%d%d",&points,&lines) == 2) { bunny=false; REP(i,points+10) { visited[i]=false; sibCnt[i] = 0; } REP(i,lines) { scanf("%d%d",&p1,&p2); sib[p1][sibCnt[p1]++] = p2; sib[p2][sibCnt[p2]++] = p1; } FOR(i,1,points) { res = 0; bfs(i); if (res >= 4) { bunny = true; break; } } //cout << endl; if (bunny) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
--- c5.s1002.cteam027.fn.cpp.0.fn.cpp +++ c5.s1067.cteam027.fn.cpp.0.fn.cpp @@ -20,4 +20,6 @@ #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl; +queue<int> q; + bool bunny; int grade[10024]; @@ -26,6 +28,7 @@ int sibCnt[10024]; int p1, p2, points, lines,res; - +/* void dfs (int node, bool first) { + int cnt = 0; if (visited[node]) return; if (first && sibCnt[node]==1) res++; @@ -35,4 +38,5 @@ for (int i = 0; i < sibCnt[node]; i++) { if (!visited[sib[node][i]]) { + if (first) cnt++; //cout << "Node " << sib[node][i] << endl; dfs (sib[node][i],false); @@ -40,6 +44,29 @@ } } + if (first && cnt==1) res++; if (!found) res++; + +} +*/ + +void bfs (int node) { + bool found = false; + if (visited[node]) return; + q.push(node); + if (sibCnt[node] == 1) res++; + while(!q.empty()) { + found = false; + node = q.front(); q.pop(); + visited[node] = true; + REP(i, sibCnt[node]) { + if (!visited[sib[node][i]]) { + q.push(sib[node][i]); + found = true; + } + } + if (!found) res++; + } + //DEBUG(res); } @@ -47,5 +74,4 @@ while(scanf("%d%d",&points,&lines) == 2) { - res = 0; bunny=false; REP(i,points+10) { @@ -58,6 +84,7 @@ sib[p2][sibCnt[p2]++] = p1; } - REP(i,points+10) { - dfs(1,true); + FOR(i,1,points) { + res = 0; + bfs(i); if (res >= 4) { bunny = true; @@ -65,5 +92,5 @@ } } - //cout << res << endl; + //cout << endl; if (bunny) cout << "YES" << endl; else cout << "NO" << endl;