# DFS
N=9
G=Array.new
N.times{|j| G[j]=Array.new  }
G[0]<<1<<2
G[1]<<0<<2<<6
G[2]<<0<<1<<3<<4
G[3]<<2<<4
G[4]<<2<<3<<5
G[5]<<4
G[6]<<1
G[7]<<8
G[8]<<7

#V is the visited array
V=Array.new
N.times{|j|V[j]=false}

#P is the parent array
P = Array.new
N.times{|j|P[j] = -1}

def dfs(i,p)

 V[i]=true
 P[i] = p

  G[i].length.times{|k| 
  if(V[G[i][k]]) then
    if(G[i][k] != P[i]) then 
      print("graph has a cycle\n") 
      exit
     end
  else
     dfs(G[i][k],i)
  end
 }
 return 
end

def notallvisited()
 j = 0
 while(j < V.length)
  if(!V[j]) then return j end
  j = j + 1
 end
 return -1 
end
 
print("Does the graph have a cycle?\n ")

while(1)
 vert  = notallvisited()
 if vert == -1 then
  break
 else
  dfs(vert,-1)
 end
end