Depth-First Search

WIKI: http://en.wikipedia.org/wiki/Depth-first_search



實作細節：

1. 比起 Non-recursive implementation, recursive implementation 會佔用較多的 memory stack，無所謂好壞，只要能符合需求的就是好程式。

2. Graph 是有向圖或者是無向圖，這很重要。

例子：http://community.topcoder.com/stat?c=problem_statement&pm=1524&rd=4472 ((可能需要登入帳號))

product 1 competes with 2 => product 2 competes with 1，所以 graph 是無向圖。

using System;
using System.Collections.Generic;

namespace TopCoder.GraphPractice
{
    class Marketing
    {
        public long howMany(String[] compete)
        {
            Dictionary<int, Vertex> graph = GetGraph(compete);

            int arrangedCount = 0;

            foreach (Vertex vertex in graph.Values)
            {
                if (!vertex.Visited)
                {
                    vertex.Consumer = ConsumerGroup.Teenagers;
                    if (HasArrangement(vertex))
                    {
                        arrangedCount++;
                    }
                    else
                    {
                        return -1;
                    }
                }
            }

            return (long)Math.Pow(2, arrangedCount);
        }

        private Dictionary<int, Vertex> GetGraph(String[] compete)
        {
            Dictionary<int, Vertex> graph = new Dictionary<int, Vertex>();
            
            for (int i = 0; i < compete.Length; i++)
            {
                graph.Add(i, new Vertex());
            }

            for (int i = 0; i < compete.Length; i++)
            {
                String[] vertexList = compete[i].Split();
                foreach (String vertex in vertexList)
                {
                    if (!String.IsNullOrEmpty(vertex))
                    {
                        int j = Int32.Parse(vertex);
                        if (!graph[i].Neighborhood.ContainsKey(j))
                        {
                            graph[i].Neighborhood.Add(j, graph[j]);
                        }
                        if (!graph[j].Neighborhood.ContainsKey(i))
                        {
                            graph[j].Neighborhood.Add(i, graph[i]);
                        }
                    }
                }
            }

            return graph;
        }

        private bool HasArrangement(Vertex vertex)
        {
            bool hasArrangement = true;

            Stack<Vertex> stack = new Stack<Vertex>();
            stack.Push(vertex);

            while (stack.Count > 0)
            {
                Vertex top = stack.Pop();
                if (top.Visited)
                {
                    continue;
                }
                top.Visited = true;
                
                foreach (Vertex neighborhood in top.Neighborhood.Values)
                {
                    if (neighborhood.Consumer == ConsumerGroup.Unknown)
                    {
                        if (top.Consumer == ConsumerGroup.Teenagers)
                        {
                            neighborhood.Consumer = ConsumerGroup.Adults;
                        }
                        else if (top.Consumer == ConsumerGroup.Adults)
                        {
                            neighborhood.Consumer = ConsumerGroup.Teenagers;
                        }
                    }
                    else
                    {
                        if (top.Consumer == neighborhood.Consumer)
                        {
                            hasArrangement = false;
                        }
                    }

                    stack.Push(neighborhood);
                }
            }

            return hasArrangement;
        }

        private class Vertex
        {
            public Dictionary<int, Vertex> Neighborhood { get; set; }

            public bool Visited { get; set; }

            public ConsumerGroup Consumer { get; set; }

            public Vertex()
            {
                Neighborhood = new Dictionary<int, Vertex>();
                Visited = false;
                Consumer = ConsumerGroup.Unknown;
            }
        }

        private enum ConsumerGroup
        {
            Unknown,
            Adults,
            Teenagers
        }
    }
}