using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using QuickGraph;

using MyVertex = System.Int32;
using MyEdge = QuickGraph.Edge<System.Int32>;//QuickGraph.SEquatableEdge<System.Int32>;

namespace CSharpTest
{
    internal class SelfAcyclicAlgorithm
    {
        private IVertexListGraph<MyVertex, MyEdge> graph;
        
        private enum VerState//: byte
        {
            NotVisited,
            InProgress,
            Processed,
        }
        
        private class CircleFound: Exception
        {
        }

        public SelfAcyclicAlgorithm(IVertexListGraph<MyVertex, MyEdge> grph)     
        {
            graph = grph;
        }

        public bool HasCycles()
        {
            Dictionary<MyVertex, VerState> dict = new Dictionary<int, VerState>(graph.VertexCount);
            /*foreach (var vertex in graph.Vertices)
            {
                dict[vertex] = VerState.NotVisited;
            }*/
            try
            {
                foreach (var vertex in graph.Vertices)
                {
                    if (!dict.ContainsKey(vertex))
                    {
                        DFS(dict, vertex);
                    }
                }
            }
            catch (CircleFound)
            {
                return true;
            }
            return false;
        }

        private void DFS(Dictionary<MyVertex, VerState> dict, MyVertex vertex)
        {
            dict[vertex] = VerState.InProgress;
            foreach (var edge in graph.OutEdges(vertex))
	        {
                MyVertex neighbour = edge.Target;
                VerState state;
                if (dict.TryGetValue(neighbour, out state))
                {
                    switch (state)
                    {
                        case VerState.InProgress:
                            throw new CircleFound();
                        case VerState.Processed:
                            break;
                    }
                }
                else
                {
                    DFS(dict, neighbour);
                }
	        }
            dict[vertex] = VerState.Processed;
            //return false;
        }
    }
}