unt311's blog

writing dfs as a lambda function
By unt311, history, 3 years ago, In English

Please share your dfs with lambda function code or improve mine.

        function<void()> dfs = [&](int a, int par, int depth) {
            vis[a] = true;
            if(depth > maxDepth){
                maxDepth = depth;
                farthestNode = a;
            }
            for(auto x: adj[a]){
                if(!vis[x])
                    dfs(x, a, 1 + dep);
            }
        };

I get the following error. error: no match for call to '(std::function<void()>) (long long int&, long long int&, long long int)'|

NOTE: changing a to &a and p to &p in parameter list does not make the error go away.

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

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have #define int long long in the beginning of my code, in case you wonder where did long long come from.

→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Try function <void(int, int, int)> instead.

→ Reply
»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

I like to write them like this:

vi col(n);
col[0] = 0;

auto dfs = [&](int u, int p, auto&& dfs) -> void {
	for (int v : adj[u])
		if (v != p) {
			col[v] = col[u] ^ 1;
			dfs(v, u, dfs);
		}
};

dfs(0, -1, dfs);
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone have the link on how to write recursive lambda and related stuff?

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

    What do you mean? How lightseba's answer not tutorial for recursive lambda?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i want to know more about lambda function(especially recursive) like why '&&' operater(not using && or single '&' also working) in ([&](int u, int p, auto&& dfs)) is used and many more...

      and yes lightseba's answer helped me to write recursive lambda function but i want know more that's why i asked for resources if anyone has..

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

        If you ask about basic knowledge, then I think you can start here and there

        Recursive lambda as lightseba's corresponds to C++14's generic lambda
        It's about labmda itself. About auto&& there no answer as I see. But you can see from paper that it is equivalent to 

        template<typename Func>
void operator()(int u, int p, Func&& dfs) {
    //...
}

        And that syntax is about universal references. Can read some information here. Don't know whether there fuller paper about it but it is hard to understand topic.
        In fact in recursive calls passes lvalue reference to lambda. auto& must work too, difference there if std::move or rvalue used to pass lambda (may not compile). auto must work too, I'd say that difference here is that lambda is copying, but I can't reproduce it.

        → Reply