Go to diff to previous submission
// // File: fs.cc // Author: cteam008 // // Created on October 19, 2013, 10:50 AM // #include <stdlib.h> #include <stdio.h> #include <iostream> #include <vector> #include <queue> using namespace std; // // // int main(int argc, char** argv) { int n, m, x, y; vector<int> deg3; bool isDeg4, same; while (cin >> n >> m) { vector<int> edges[n+1]; int deg[n+1]; for (int i = 0; i <= n; i++) { deg[i] = 0; } deg3.clear(); isDeg4 = false; for (int i = 0; i < m; i++) { cin >> x >> y; deg[x]++; if (deg[x] >= 4) { isDeg4 = true; } else { if (deg[x] == 3) { deg3.push_back(x); } edges[x].push_back(y); } deg[y]++; if (deg[y] >= 4) { isDeg4 = true; } else { if (deg[y] == 3) { deg3.push_back(y); } edges[y].push_back(x); } } if (isDeg4) { cout << "YES" << endl; continue; } if (deg3.size() < 2) { cout << "NO" << endl; continue; } for (int i = 1; i < deg3.size(); i++) { vector<bool> used(n+1, false); x = deg3[i]; used[x]=true; queue<int> fifo; for (int j = 0; j < 3; j++) { y =edges[x][j]; if (deg[y] == 2) { used[y]=true; y = (edges[y][0] == x) ? edges[y][1] : edges[y][0]; } if (deg[y] == 3) { same = false; for (int h = 0; h < 3; h++) { if (!used[edges[x][h]]) { for (int k = 0; k < 3; k++) { if (edges[x][h]==edges[y][k]) { same = true; break; } } } if (same) break; } if (!same) { isDeg4 = true; break; } fifo.push(y); } else if (deg[y] > 1) { fifo.push(y); } used[y]=true; } if (isDeg4) { break; } while (!fifo.empty()) { x = fifo.front(); fifo.pop(); for (int j = 0; j < deg[x]; j++) { y = edges[x][j]; if (!used[y]) { if (deg[y] == 3) { isDeg4 = true; break; } fifo.push(y); } } if (isDeg4) { break; } } } if (isDeg4) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return (EXIT_SUCCESS); }
--- c5.s1048.cteam008.fn.cpp.0.fn.cpp +++ c5.s1130.cteam008.fn.cpp.0.fn.cpp @@ -19,5 +19,5 @@ // int main(int argc, char** argv) { - int n, m, x, y, z; + int n, m, x, y; vector<int> deg3; bool isDeg4, same; @@ -66,27 +66,12 @@ for (int j = 0; j < 3; j++) { y =edges[x][j]; + if (deg[y] == 2) { + used[y]=true; + y = (edges[y][0] == x) ? edges[y][1] : edges[y][0]; + } if (deg[y] == 3) { same = false; for (int h = 0; h < 3; h++) { - for (int k = 0; k < 3; k++) { - if (edges[x][h]==edges[y][k]) { - same = true; - break; - } - } - if (same) break; - } - if (!same) { - isDeg4 = true; - break; - } - used[y]=true; - fifo.push(y); - } else if (deg[y] == 2) { - used[y]=true; - y = (edges[y][0] == x) ? edges[y][1] : edges[y][0]; - if (deg[y] == 3) { - same = false; - for (int h = 0; h < 3; h++) { + if (!used[edges[x][h]]) { for (int k = 0; k < 3; k++) { if (edges[x][h]==edges[y][k]) { @@ -95,16 +80,16 @@ } } - if (same) break; - } - if (!same) { - isDeg4 = true; - break; } + if (same) break; } - used[y]=true; - if (deg[y] > 1) { - fifo.push(y); + if (!same) { + isDeg4 = true; + break; } + fifo.push(y); + } else if (deg[y] > 1) { + fifo.push(y); } + used[y]=true; } if (isDeg4) { @@ -132,11 +117,8 @@ } if (isDeg4) { - cout << "YES" << endl; - + cout << "YES" << endl; } else { cout << "NO" << endl; - } - - + } } return (EXIT_SUCCESS);