i am not understanding the syntax of this dfs implementation

Question

this a dfs funciton code snippet:-

void dfs(int u, int p)
            {
                if(p!=-1)d[u] = d[p]+1;
                for(int i: v[u])
                {
                    if(i==p)continue;
                    dfs(i, u);
                }
            }

i am not understanding this dfs implementation which came in the editorial of of a contest. the complete code is as follows.it would be really nice if someone could help me understand this piece of code

#include <bits/stdc++.h>
        using namespace std;
        #define int long long int

        vector<int> d;
        vector< vector<int> > v;

        void dfs(int u, int p)
        {
            if(p!=-1)d[u] = d[p]+1;
            for(int i: v[u])
            {
                if(i==p)continue;
                dfs(i, u);
            }
        }

#undef int
int main()
{
#define int long long int
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n;
cin>>n;
v.resize(n);
d.resize(n);
for(int i = 0;i<n-1;i++)
{
    int x, y;
    cin>>x>>y;
    v[x-1].push_back(y-1);
    v[y-1].push_back(x-1);
}
d[0] = 0;
dfs(0, -1);
int q;
cin>>q;
while(q--)
{
    int x, y;
    cin>>x>>y;
    if((d[x-1]+d[y-1])&1)cout<<"Odd"<<endl;
    else cout<<"Even"<<endl;
}


return 0;

}

Code submitted to "constest" sites or "online judges" tend to be badly written and quick hacks that no one really should use as learning material. Case in point: Redefining with a macro a basic built-in type; [Including ``](http://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h); Badly named variables; No documentation or comments. If you want to learn to program C++ then [read good books](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or go to school. — Some programmer dude, Oct 18 '17 at 06:29
Nothing spices up your code like redefining a keyword. Next up `#define double float` — Passer By, Oct 18 '17 at 06:35
@Someprogrammerdude few days ago I was scrutinizing some exam papers for next phase of fresher recruitment at our office. And I was surprised that literally everyone included `bits/stdc++.h`. I asked others which books students follow mainly these days and one of my younger colleagues replied that `Code::Blocks` auto generate this. — taskinoor, Oct 18 '17 at 06:51
@taskinoor I just tried with Code::Blocks, and unless your colleague uses a *very* old version (much older than the last binary release which is almost two years old) it does not generate that include. — Some programmer dude, Oct 18 '17 at 07:02
@Someprogrammerdude I'm not sure, never tried Code::Blocks myself. My colleague used it at least five years back. Don't know why students just passing our from school are including that thing. Maybe I will ask them if I get a chance for face-to-face interview. — taskinoor, Oct 18 '17 at 07:20

user2736738 · Accepted Answer · 2017-10-18T06:43:29.860

This is the standard dfs code.

Root's parent is -1. So in every other case we will have a parent.

For all that nodes we will visit it's neighbors.

            for(int i: v[u]) // every neighbor of u except the parent.
            {
                if(i==p)continue; // avoiding the parent from which it is traversed
                dfs(i, u); // recursively search there.
            }

In case you are interested in the c++ language details that is being used you can try this reference.

Also there are more readable way to do the same thing. But in case of competitive coding that is not entertained due to time constraint on the part of coding. That is why it is a bad place to learn about any good practices.

You can additionally replace the code in the for-loop with something like this

   for(int neighborNodeIndx = 0 ; neighborNodeIndx <  (int)v[u].size(); neighborNodeIndx ++)
  {
       neighborNode = v[u][neighborNodeIndx];// this is similar to i
       ...
  }

i am not understanding the syntax of this dfs implementation

1 Answers1