Go to diff to previous submission
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<cctype> #include<climits> #include<algorithm> #include<utility> #include<string> #include<deque> #include<list> #include<map> #include<queue> #include<set> #include<stack> #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 FORI(i,a,b) for (int i = (a); i < (b); i++) #define FORD(i,a,b) for (int i = (a)-1; i >= (b); i--) #define DP(arg...) fprintf(stderr, ## arg) typedef long long ll; typedef long double ld; typedef pair<int,int> ii; int N,M; vector<int> E[11000]; int deg[11000]; int vis[11000]; int d3, d4; void dfs(int v) { //DP("%d ", v); if (deg[v] >= 3) d3++; if (deg[v] >= 4) d4++; vis[v] = 1; REP(i,E[v].size()) { if (!vis[E[v][i]]) dfs(E[v][i]); } } void solve() { REP(i,N) { deg[i] = 0; E[i].clear(); vis[i] = 0; } REP(i,M) { int a,b; scanf("%d%d", &a, &b); a--; b--; deg[a]++; deg[b]++; E[a].push_back(b); E[b].push_back(a); } REP(k,N) { d3 = 0, d4 = 0; if (!vis[k]) dfs(k); if (d3 >= 2 || d4 >= 1) { printf("YES\n"); return; } } printf("NO\n"); } int main() { while (scanf("%d%d", &N, &M) != EOF) { solve(); } return 0; }
--- c5.s453.cteam022.fn.cpp.0.fn.cpp +++ c5.s516.cteam022.fn.cpp.0.fn.cpp @@ -32,14 +32,35 @@ int N,M; -//vector<int> E[11000]; +vector<int> E[11000]; int deg[11000]; +int vis[11000]; +int d3, d4; + +void dfs(int v) { + //DP("%d ", v); + if (deg[v] >= 3) d3++; + if (deg[v] >= 4) d4++; + vis[v] = 1; + REP(i,E[v].size()) { + if (!vis[E[v][i]]) + dfs(E[v][i]); + } +} void solve() { - REP(i,N) deg[i] = 0; + REP(i,N) { deg[i] = 0; E[i].clear(); vis[i] = 0; } REP(i,M) { int a,b; - scanf("%d%d", &a, &b); deg[a-1]++; deg[b-1]++; - + scanf("%d%d", &a, &b); + a--; b--; + deg[a]++; deg[b]++; + E[a].push_back(b); + E[b].push_back(a); + + } + REP(k,N) { + d3 = 0, d4 = 0; + if (!vis[k]) dfs(k); + if (d3 >= 2 || d4 >= 1) { printf("YES\n"); return; } } - REP(i,N) { if (deg[i] >= 4) { printf("YES\n"); return; } } printf("NO\n");