Go to diff to previous submission
#include <cstdlib> #include <cstdio> #include <cstring> #include <vector> #include <iostream> using namespace std; struct Node{ Node(){ visited = false; paw = false; body = false; } bool visited; bool paw; bool body; vector<int> edges; }; vector<Node> nodes; bool tri = false; bool hasZajac(int node){ if(nodes[node].visited) return false; nodes[node].visited = true; if(nodes[node].edges.size()==3){ if(tri) { int pawConflicts = 0; for (int i=0; i<3; i++) { if (nodes[nodes[node].edges[i]].paw) pawConflicts++; } if (pawConflicts < 2) { return true; } } else { tri = true; //cout << "Node: " << node+1 << endl; for (int i=0; i<3; i++) { //cout << nodes[node].edges[i] << " is paw." << endl; nodes[nodes[node].edges[i]].paw = true; } nodes[node].body = true; } } if(nodes[node].edges.size() > 3 ){ return true; } for( int i = 0; i < nodes[node].edges.size(); i++ ){ if(hasZajac(nodes[node].edges[i])) return true; } return false; } int main(int argc, char * argv[]){ int n,m,a,b; while(scanf("%d%d",&n,&m)==2){ nodes.resize(0); nodes.resize(n); for( int i = 0; i < m; i++ ){ scanf("%d%d",&a,&b); a--; b--; nodes[a].edges.push_back(b); nodes[b].edges.push_back(a); } bool zajacfound = false; for( int i = 0; i < nodes.size(); i++ ){ if(!nodes[i].visited){ tri = false; if(hasZajac(i)){ zajacfound = true; break; } } } printf("%s\n",zajacfound?"YES":"NO"); } return 0; }
--- c5.s737.cteam045.fn.cpp.0.furry.cpp +++ c5.s997.cteam045.fn.cpp.0.furry.cpp @@ -3,4 +3,5 @@ #include <cstring> #include <vector> +#include <iostream> using namespace std; @@ -10,35 +11,48 @@ visited = false; paw = false; + body = false; } bool visited; bool paw; + bool body; vector<int> edges; }; vector<Node> nodes; +bool tri = false; -bool hasZajac(int node,bool tri){ +bool hasZajac(int node){ if(nodes[node].visited) return false; + nodes[node].visited = true; + if(nodes[node].edges.size()==3){ if(tri) { - for (int i=0; i<nodes[node].edges.size(); i++) { - if (nodes[nodes[node].edges[i]].paw) { - return false; - } + int pawConflicts = 0; + for (int i=0; i<3; i++) { + if (nodes[nodes[node].edges[i]].paw) + pawConflicts++; } - return true; - } - for (int i=0; i<nodes[node].edges.size(); i++) { - nodes[i].paw = true; + if (pawConflicts < 2) { + return true; + } + } else { + tri = true; + //cout << "Node: " << node+1 << endl; + for (int i=0; i<3; i++) { + //cout << nodes[node].edges[i] << " is paw." << endl; + nodes[nodes[node].edges[i]].paw = true; + } + nodes[node].body = true; } - tri = true; } + if(nodes[node].edges.size() > 3 ){ return true; } + for( int i = 0; i < nodes[node].edges.size(); i++ ){ - if(hasZajac(nodes[node].edges[i],tri)) + if(hasZajac(nodes[node].edges[i])) return true; } @@ -61,5 +75,6 @@ for( int i = 0; i < nodes.size(); i++ ){ if(!nodes[i].visited){ - if(hasZajac(i,false)){ + tri = false; + if(hasZajac(i)){ zajacfound = true; break;