aa0809's blog

Help find the error in this dfs
By aa0809, history, 5 years ago, In English

Hi,

I was working on this problem: https://codeforces.net/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://codeforces.net/contest/771/submission/69394496 AC submission: https://codeforces.net/contest/771/submission/69395025

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Let's say you make the first call dfs2(u) and then your condition : if(adj[u].size() != cur_sz — 1) is not true then you will always return true. 

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]) // you need to return what dfs2(v) gives u
			dfs2(v);

	return true; 
}

But thatshould not be the answer because imagine you have and edge (u,v) and then you call dfs2(v) and for v the condition if(adj[v].size() != cur_sz — 1) is true, then ur answer should be false. But you are always returing true because the call dfs(u) does that.

Hope it helps :)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank you so much for the detailed explanation! This answered my question.

    → Reply