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; grade[i] = 0; } REP(i,lines) { scanf("%d%d",&p1,&p2); sib[p1][sibCnt[p1]++] = p2; sib[p2][sibCnt[p2]++] = p1; grade[p1]++; grade[p2]++; } FOR(i,1,points) { FOR(j,1,points) visited[i]=false; res = 0; bfs(i); if (res >= 4 || grade[i] >= 4) { bunny = true; break; } } //cout << endl; if (bunny) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
--- c5.s1074.cteam027.fn.cpp.0.fn.cpp +++ c5.s1104.cteam027.fn.cpp.0.fn.cpp @@ -78,4 +78,5 @@ visited[i]=false; sibCnt[i] = 0; + grade[i] = 0; } REP(i,lines) { @@ -83,4 +84,6 @@ sib[p1][sibCnt[p1]++] = p2; sib[p2][sibCnt[p2]++] = p1; + grade[p1]++; + grade[p2]++; } FOR(i,1,points) { @@ -88,5 +91,5 @@ res = 0; bfs(i); - if (res >= 4) { + if (res >= 4 || grade[i] >= 4) { bunny = true; break;