public class Graph
    {
        private int v;
        private int e;
        private List<int>[] adj; //鄰接表(用List 代替  bag)

        /// <summary>
        /// 創(chuàng)建一個(gè)含有V個(gè)頂點(diǎn)但不含有邊的圖
        /// </summary>
        /// <param name="V"></param>
        public Graph(int V)
        {
            v = V;
            e = 0;
            adj = new List<int>[V];
            for (var i = 0; i < V; i++)
                adj[i] = new List<int>();
        }

        public Graph(string[] strs)
        {
            foreach (var str in strs)
            {
                var data = str.Split(' ');
                int v = Convert.ToInt32(data[0]);
                int w = Convert.ToInt32(data[1]);
                AddEdge(v,w);
            }
        }

        /// <summary>
        /// 頂點(diǎn)數(shù)
        /// </summary>
        /// <returns></returns>
        public int V()
        {
            return v;
        }

        /// <summary>
        /// 邊數(shù)
        /// </summary>
        /// <returns></returns>
        public int E()
        {
            return e;
        }

        /// <summary>
        /// 向圖中添加一條邊 v-w
        /// </summary>
        /// <param name="v"></param>
        /// <param name="w"></param>
        public void AddEdge(int v, int w)
        {
            adj[v].Add(w);
            adj[w].Add(v);
            e++;
        }

        /// <summary>
        /// 和v相鄰的所有頂點(diǎn)
        /// </summary>
        /// <param name="v"></param>
        /// <returns></returns>
        public IEnumerable<int> Adj(int v)
        {
            return adj[v];
        }

        /// <summary>
        /// 計(jì)算 V 的度數(shù)
        /// </summary>
        /// <param name="G"></param>
        /// <param name="V"></param>
        /// <returns></returns>
        public static int Degree(Graph G, int V)
        {
            int degree = 0;
            foreach (int w in G.Adj(V))
                degree++;
            return degree;
        }

        /// <summary>
        /// 計(jì)算所有頂點(diǎn)的最大度數(shù)
        /// </summary>
        /// <param name="G"></param>
        /// <returns></returns>
        public static int MaxDegree(Graph G)
        {
            int max = 0;
            for (int v = 0; v < G.V(); v++)
            {
                var d = Degree(G, v);
                if (d > max)
                    max = d;
            }
            return max;
        }

        /// <summary>
        /// 計(jì)算所有頂點(diǎn)的平均度數(shù)
        /// </summary>
        /// <param name="G"></param>
        /// <returns></returns>
        public static double AvgDegree(Graph G)
        {
            return 2.0 * G.E() / G.V();
        }

        /// <summary>
        /// 計(jì)算自環(huán)的個(gè)數(shù)
        /// </summary>
        /// <param name="G"></param>
        /// <returns></returns>
        public static int NumberOfSelfLoops(Graph G)
        {
            int count = 0;
            for (int v = 0; v < G.V(); v++)
            {
                foreach (int w in G.Adj(v))
                {
                    if (v == w)
                        count++;
                }
            }

            return count / 2; //每條邊都被計(jì)算了兩次
        }

        public override string ToString()
        {
            string s = V() + " vertices, " + E() + " edges\n";
            for (int v = 0; v < V(); v++)
            {
                s += v + ":";
                foreach (int w in Adj(v))
                {
                    s += w + " ";
                }
                s += "\n";
            }
            return s;
        }
    }

namespace Graphs
{
    /// <summary>
    /// 使用一個(gè) bool 數(shù)組來記錄和起點(diǎn)連通地所有頂點(diǎn)。遞歸方法會(huì)標(biāo)記給定地頂點(diǎn)并調(diào)用自己來訪問該頂點(diǎn)地相鄰頂點(diǎn)列表中
    /// 所有沒有被標(biāo)記過地頂點(diǎn)。 如果圖是連通的，每個(gè)鄰接鏈表中的元素都會(huì)被標(biāo)記。
    /// </summary>
    public class DepthFirstSearch
    {
        private bool[] marked;
        private int count;

        public DepthFirstSearch(Graph G,int s)
        {
            marked = new bool[G.V()];
            Dfs(G,s);
        }

        private void Dfs(Graph g, int V)
        {
            marked[V] = true;
            count++;
            foreach (var w in g.Adj(V))
            {
                if (!marked[w])
                    Dfs(g,w);
            }
        }

        public bool Marked(int w)
        {
            return marked[w];
        }
    }
}

    public class DepthFirstPaths
    {
        private bool[] marked;
        private int[] edgeTo; //從起點(diǎn)到一個(gè)頂點(diǎn)的已知路徑上的最后一個(gè)頂點(diǎn)
        private int s;//起點(diǎn)

        public DepthFirstPaths(Graph G, int s)
        {
            marked = new bool[G.V()];
            edgeTo = new int[G.V()];
            this.s = s;
            Dfs(G,s);
        }

        private void Dfs(Graph G, int v)
        {
            marked[v] = true;
            foreach (int w in G.Adj(v))
            {
                if (!marked[w])
                {
                    edgeTo[w] = v;
                    Dfs(G,w);
                }
            }
        }

        public bool HasPathTo(int v)
        {
            return marked[v];
        }

        public IEnumerable<int> PathTo(int v)
        {
            if (!HasPathTo(v))
                return null;
            Stack<int> path = new Stack<int>();
            for (int x = v; x != s; x = edgeTo[x])
                path.Push(x);
            path.Push(s);
            return path;
        }
    }

namespace Graphs
{
    /// <summary>
    /// 廣度優(yōu)先搜索
    /// </summary>
    public class BreadthFirstPaths
    {
        private bool[] marked;//到達(dá)該頂點(diǎn)的最短路徑已知嗎？
        private int[] edgeTo;//到達(dá)該頂點(diǎn)的已知路徑上的最后一個(gè)頂點(diǎn)
        private int s;//起點(diǎn)

        public BreadthFirstPaths(Graph G,int s)
        {
            marked = new bool[G.V()];
            edgeTo = new int[G.V()];
            this.s = s;
            Bfs(G,s);
        }

        private void Bfs(Graph G, int s)
        {
            Queue<int> queue = new Queue<int>();
            marked[s] = true;//標(biāo)記起點(diǎn)
            queue.Enqueue(s);//將它加入隊(duì)列
            while (queue.Count > 0)
            {
                int v = queue.Dequeue();//從隊(duì)列中刪去下一個(gè)頂點(diǎn)
                foreach (var w in G.Adj(v))
                {
                    if (!marked[w])//對(duì)于每個(gè)未標(biāo)記的相鄰頂點(diǎn)
                    {
                        edgeTo[w] = v;//保存最短路徑的最后一條邊
                        marked[w] = true;//標(biāo)記它，因?yàn)樽疃搪窂揭阎?
                        queue.Enqueue(w);//并將它添加到隊(duì)列中
                    }
                }
            }
        }

        public bool HasPathTo(int v)
        {
            return marked[v];
        }
    }
}

namespace Graphs
{
    public class CC
    {
        private bool[] marked;
        private int[] id;
        private int count;

        public CC(Graph G)
        {
            marked = new bool[G.V()];
            id = new int[G.V()];
            for (var s = 0; s < G.V(); s++)
            {
                if (!marked[s])
                {
                    Dfs(G,s);
                    count++;
                }
            }
        }

        private void Dfs(Graph G, int v)
        {
            marked[v] = true;
            id[v] = count;
            foreach (var w in G.Adj(v))
            {
                if (!marked[w])
                    Dfs(G,w);
            }
        }

        public bool Connected(int v, int w)
        {
            return id[v] == id[w];
        }

        public int Id(int v)
        {
            return id[v];
        }

        public int Count()
        {
            return count;
        }
    }
}

namespace Graphs
{
    public class Cycle
    {
        private bool[] marked;
        private bool hasCycle;

        public Cycle(Graph G)
        {
            marked = new bool[G.V()];
            for (var s = 0; s < G.V(); s++)
            {
                if (!marked[s])
                    Dfs(G,s,s);
            }
        }

        private void Dfs(Graph g, int v, int u)
        {
            marked[v] = true;
            foreach (var w in g.Adj(v))
            {
                if (!marked[w])
                    Dfs(g, w, v);
                else if (w != u)
                    hasCycle = true;
            }
        }

        public bool HasCycle()
        {
            return hasCycle;
        }
    }
}

namespace Graphs
{
    public class TwoColor
    {
        private bool[] marked;
        private bool[] color;
        private bool isTwoColorable = true;

        public TwoColor(Graph G)
        {
            marked = new bool[G.V()];
            color = new bool[G.V()];
            for(var s = 0;s<G.V();s++)
            {
                if (!marked[s])
                    Dfs(G,s);
            }
        }

        private void Dfs(Graph g, int v)
        {
            marked[v] = true;
            foreach (var w in g.Adj(v))
            {
                if (!marked[w])
                {
                    color[w] = !color[v];
                    Dfs(g, w);
                }
                else if (color[w] == color[v])
                    isTwoColorable = false;
            }
        }

        public bool IsBipartite()
        {
            return isTwoColorable;
        }
    }
}

namespace Graphs
{
    public class SymbolGraph
    {
        private Dictionary<string, int> st;//符號(hào)名 -> 索引
        private string[] keys;//索引 -> 符號(hào)名
        private Graph G;

        public SymbolGraph(string fileName, string sp)
        {
            var strs = File.ReadAllLines(fileName);
            st = new Dictionary<string, int>();

            //第一遍
            foreach (var str in strs)
            {
                var _strs = str.Split(sp);
                foreach (var _str in _strs)
                {
                    st.Add(_str,st.Count);
                }
            }

            keys = new string[st.Count];
            foreach (var name in st.Keys)
            {
                keys[st[name]] = name;
            }

            //第二遍 將每一行的第一個(gè)頂點(diǎn)和該行的其他頂點(diǎn)相連
            foreach (var str in strs)
            {
                var _strs = str.Split(sp);
                int v = st[_strs[0]];
                for (var i = 1; i < _strs.Length; i++)
                {
                    G.AddEdge(v,st[_strs[i]]);
                }
            }
        }

        public bool Contains(string s)
        {
            return st.ContainsKey(s);
        }

        public int Index(string s)
        {
            return st[s];
        }

        public string Name(int v)
        {
            return keys[v];
        }

        public Graph Gra()
        {
            return G;
        }
    }
}