Source code for submission s997

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;
}
 

Diff to submission s737

--- 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;