Help find the error in this dfs

Правка en3, от aa0809, 2020-01-23 08:57:03

Hi,

I was working on this problem: https://mirror.codeforces.com/contest/771/problem/A

By adding a return in front of my recursive call in the function "dfs2," I was able to get AC on this problem. Can anyone please explain why?

Difference:

bool dfs2(int u)
{
	if(vis[u])
		return false;
	vis[u] = 1;
	if(adj[u].size() != cur_sz - 1)
		return false;
	for(int v : adj[u])
		if(!vis[v])
			dfs2(v);
	return true;
}

as opposed to

bool dfs2(int u)
{
	if(vis[u])
		return false;
	vis[u] = 1;
	if(adj[u].size() != cur_sz - 1)
		return false;
	for(int v : adj[u])
		if(!vis[v])
			return dfs2(v);
	return true;
}

WA submission: https://mirror.codeforces.com/contest/771/submission/69394496 AC submission: https://mirror.codeforces.com/contest/771/submission/69395025

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский aa0809 2020-01-23 08:57:03 0 (published)
en2 Английский aa0809 2020-01-23 08:56:38 9 (saved to drafts)
en1 Английский aa0809 2020-01-23 08:55:46 842 Initial revision (published)