In-Out time of nodes

PHOTO

Mon Jan 10 2022 06:55:32 GMT+0000 (Coordinated Universal Time)

            vector g[100001];
            vector visi(100001, 0);

          //-> in out time of a node
          vector In(100001);
          vector Out(100001);
          ll Time = 1;
          
          void in_out_time(ll v)
          {
              visi[v] = 1;
              In[v] = Time;
              Time++;
              for (ll child : g[v]) {
                  if (visi[child] == 0)
                      in_out_time(child);
              }
          
              Out[v] = Time;
              Time++;
          
          }

COPY

This, a important concept as it will be further used in beidges,articulation point,etc. Major,application of in/out time is that we can tell weather one node lies in subtree of other if x lies in subtree of y then, IN[x] > IN[y] && OUT[x] < OUT[y]