Go to diff to previous submission
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <vector> #include <cstring> using namespace std; #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++) #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--) #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--) #define PB push_back #define MP make_pair #define MM(co, cim) memset((co), (cim), sizeof((co))) #define DEB(x) cerr << ">>> " << #x << " : " << x << endl; int p[10005], mdeg, mn, cnt, d[10014]; vector<int> g[10014]; queue<int> q; int main () { int m,n,a,b; while(cin >> n >> m){ FOR(i, 0, 10014) g[i].clear(); mdeg = 0; MM(p,0); MM(d,-1); FOR(i,0,m){ cin >> a >> b; p[a]++; p[b]++; g[a].PB(b); g[b].PB(a); if (p[a] > mdeg) { mdeg = p[a]; mn = a; } if (p[b] > mdeg) { mdeg = p[b]; mn = b; } } cnt = 0; q.push(mn); d[mn] = 0; while (!q.empty()) { int x = q.front(); q.pop(); int temp = 0; for (int i = 0; i < g[x].size(); i++) if (d[g[x][i]] == -1) { d[g[x][i]] = d[x] + 1; ++temp; q.push(g[x][i]); } if (!temp) ++cnt; } printf("%s\n", cnt >= 4 ? "YES" : "NO"); } return 0; }
--- c5.s539.cteam011.fn.cpp.0.fn.cpp +++ c5.s864.cteam011.fn.cpp.0.fn.cpp @@ -24,5 +24,7 @@ #define DEB(x) cerr << ">>> " << #x << " : " << x << endl; -int p[10005]; +int p[10005], mdeg, mn, cnt, d[10014]; +vector<int> g[10014]; +queue<int> q; int main () @@ -30,23 +32,41 @@ int m,n,a,b; while(cin >> n >> m){ + FOR(i, 0, 10014) g[i].clear(); + mdeg = 0; MM(p,0); + MM(d,-1); FOR(i,0,m){ cin >> a >> b; - p[a-1] ++; - p[b-1] ++; - - - } - bool ok = false; - FOR(i,0,n) - if(p[i] >= 4){ - ok = true; - break; + p[a]++; + p[b]++; + g[a].PB(b); + g[b].PB(a); + if (p[a] > mdeg) + { + mdeg = p[a]; + mn = a; } - - if(ok) - cout << "YES" << endl; - else - cout << "NO" << endl; + if (p[b] > mdeg) + { + mdeg = p[b]; + mn = b; + } + } + cnt = 0; + q.push(mn); + d[mn] = 0; + while (!q.empty()) + { + int x = q.front(); q.pop(); + int temp = 0; + for (int i = 0; i < g[x].size(); i++) if (d[g[x][i]] == -1) + { + d[g[x][i]] = d[x] + 1; + ++temp; + q.push(g[x][i]); + } + if (!temp) ++cnt; + } + printf("%s\n", cnt >= 4 ? "YES" : "NO"); }