using System;

using System.Collections.Generic;                   

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        Graph g = new Graph();

        g.AddEdge(0, 1);

        g.AddEdge(1, 2);

        g.AddEdge(0, 3);

        g.AddEdge(3, 4);

        g.AddEdge(4, 5);

        g.AddEdge(5, 1);

        g.AddEdge(2, 0);

​

        Console.WriteLine(g.IsCyclic());

    }

}

​

public class Node

{

    public List<Node> adjacents;

    public int data;

    public int Weight;

    public Node(int data)

    {

        adjacents = new List<Node>();

        this.data = data;

    }

} 

​

public class Graph

{

    private List<Node> Nodes;

    public Graph()

    {

        Nodes = new List<Node>();

    }

    public void AddEdge(int source,int destination)

    {

        AddEdge(source,destination,0);

    }

    public void AddEdge(int source,int destination,int weight)

    {

        var sourceNode = GetNode(source);

        var destinationNode = GetNode(destination);

        if ( sourceNode == null )

        {

            sourceNode = new Node(source);

        }

        if ( destinationNode == null )

        {

            destinationNode = new Node(destination);

​

        }

        sourceNode.adjacents.Add(destinationNode);

        Nodes.Add(sourceNode);

        Nodes.Add(destinationNode);

    }

    public void PrintAdjacentNodes(int parent)

    {

        var parentNode = GetNode(parent);

        foreach(var item in parentNode.adjacents)

        {

            Console.WriteLine(item.data);

        }

    }

    private Node GetNode(int vertex)

    {

        foreach(var item in Nodes)

        {

            if (item.data == vertex)

                return item;

        }

        return null;

    }

    public bool IsCyclic()

    {

        List<int> white = new List<int>();

        List<int> grey = new List<int>();

        List<int> black = new List<int>();

        foreach(var item in Nodes)

        {

            white.Add(item.data);

            if ( HasCycle(white,grey,black,item))

            {

                return true;

            }

​

        }

        return false;

    }

    private bool HasCycle(List<int> white,List<int> grey,List<int> black,Node vertex )

    {

        MoveVertex(white,grey,vertex.data);

        foreach(var node in vertex.adjacents)

        {

            if ( black.Contains(node.data))

                continue;

            if ( grey.Contains(node.data))

                return true;

            if ( HasCycle(white,grey,black,node))

                return true;

        }

        MoveVertex(grey,black,vertex.data);

        return false;

    }

    private void MoveVertex(List<int> source,List<int> destination,int data)

    {

        source.Remove(data);

        destination.Add(data);

    }

​

​

}