Source code for submission s761

Go to diff to previous submission

#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <string>
 
using namespace std;
 
vector< vector<int> > G;
bool marked[1000000];
bool ok = false;
 
void dfs(int v, int good)
{
	if(G[v].size() >= 4)
		ok = true;
	else if(G[v].size() == 3)
		good++;
 
	if(good == 2)
		ok = true;
 
	if(ok)
		return;
 
	marked[v] = true;
 
	for(int i=0; !ok && i<G[v].size(); i++)
	{
		int u = G[v][i];
		if(marked[u])
			continue;
		dfs(u,good);
	}
}
 
int main()
{
	int N, M;
	while(scanf("%d %d", &N, &M) == 2)
	{
		G = vector< vector<int> >(N);
		for(int i=0; i<N; i++)
		{
			G[i] = vector<int>();
			marked[i] = false;
		}
		for(int i=0; i<M; i++)
		{
			int x, y;
			scanf("%d %d", &x, &y);
			--x;
			--y;
			G[x].push_back(y);
			G[y].push_back(x);
		}
		ok = false;
		for(int i=0; !ok && i<N; i++)
		{
			if(!marked[i])
				dfs(i,0);
		}
		if(!ok)
			puts("NO");
		else
			puts("YES");
	}
 
	return 0;	
}
 

Diff to submission s563

--- c5.s563.cteam036.fn.cpp.0.fn.cpp
+++ c5.s761.cteam036.fn.cpp.0.fn.cpp
@@ -9,17 +9,42 @@
 using namespace std;
 
+vector< vector<int> > G;
+bool marked[1000000];
+bool ok = false;
+
+void dfs(int v, int good)
+{
+        if(G[v].size() >= 4)
+                ok = true;
+        else if(G[v].size() == 3)
+                good++;
+        
+        if(good == 2)
+                ok = true;
+                
+        if(ok)
+                return;
+        
+        marked[v] = true;
+
+        for(int i=0; !ok && i<G[v].size(); i++)
+        {
+                int u = G[v][i];
+                if(marked[u])
+                        continue;
+                dfs(u,good);
+        }
+}
+
 int main()
 {
-        vector< set<int> > G;
-        vector< int > C;
         int N, M;
         while(scanf("%d %d", &N, &M) == 2)
         {
-                G = vector< set<int> >(N);
-                C = vector< int >(N);
+                G = vector< vector<int> >(N);
                 for(int i=0; i<N; i++)
                 {
-                        G[i] = set<int>();
-                        C[i] = 0;
+                        G[i] = vector<int>();
+                        marked[i] = false;
                 }
                 for(int i=0; i<M; i++)
@@ -29,21 +54,17 @@
                         --x;
                         --y;
-                        G[x].insert(y);
-                        G[y].insert(x);
-                        C[x]++;
-                        C[y]++;
+                        G[x].push_back(y);
+                        G[y].push_back(x);
                 }
-                bool ok = false;
-                for(int i=0; i<N; i++)
+                ok = false;
+                for(int i=0; !ok && i<N; i++)
                 {
-                        if(G[i].size() >= 4)
-                        {
-                                puts("YES");
-                                ok = true;
-                                break;
-                        }
+                        if(!marked[i])
+                                dfs(i,0);
                 }
                 if(!ok)
                         puts("NO");
+                else
+                        puts("YES");
         }