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; 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) { 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]]) { //cout << "Node " << sib[node][i] << endl; dfs (sib[node][i],false); found = true; } } if (!found) res++; } int main() { while(scanf("%d%d",&points,&lines) == 2) { res = 0; 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; } REP(i,points+10) { dfs(1,true); if (res >= 4) { bunny = true; break; } } //cout << res << endl; if (bunny) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
--- c5.s465.cteam027.fn.cpp.0.fn.cpp +++ c5.s1002.cteam027.fn.cpp.0.fn.cpp @@ -20,17 +20,50 @@ #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl; +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) { + 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]]) { + //cout << "Node " << sib[node][i] << endl; + dfs (sib[node][i],false); + found = true; + } + } + if (!found) res++; + +} + int main() { - bool bunny; - int grade[10024]; - int p1, p2, points, lines; + while(scanf("%d%d",&points,&lines) == 2) { - bunny = false; - REP(i,points+10) grade[i] = 0; + res = 0; + bunny=false; + REP(i,points+10) { + visited[i]=false; + sibCnt[i] = 0; + } REP(i,lines) { scanf("%d%d",&p1,&p2); - grade[p1]++; - grade[p2]++; - if (grade[p1] >= 4 || grade[p2] >= 4) bunny = true; + sib[p1][sibCnt[p1]++] = p2; + sib[p2][sibCnt[p2]++] = p1; + } + REP(i,points+10) { + dfs(1,true); + if (res >= 4) { + bunny = true; + break; + } } + //cout << res << endl; if (bunny) cout << "YES" << endl; else cout << "NO" << endl;