Cycle detection in directed graph

PHOTO EMBED

Mon Jan 10 2022 06:54:45 GMT+0000 (Coordinated Universal Time)

Saved by @vaibhav_55

	      vector g[100001];
          vector visi(100001, 0);
          // -->cycle detection for directed graph
          bool is_cycle(ll v)
            {
                visi[v] = 1;
            
            
                for (ll child : g[v]) {
                    if (visi[child] == 0) {
                        if (is_cycle(child) == true)
                            return true;
                    }
                    else {
                        if (visi[child] == 1)
                            return true;
                    }
                }
            
                visi[v] = 2;
                return false;
            }

            //here,in visi array we keep the execution state of each node where 
            //0-> not visited,
            //1-> under dfs call 
            //2-> dfs call completed after visiting all the child's
         
content_copyCOPY