第一步 建立有向图

• 除去重复单词

• 输入单词words → 有向图

• 即使通过n*n矩阵表示图的边，给矩阵赋值过程还是需要空间复杂度

  不如直接时间换空间

  /*** 没仔细看语法，当伪代码吧，意会意会~ ***/
  
  // HashMap：字母s->以s开头的单词集合
  Dictionary<char, Arraylist<Node>> startLetter_to_nodes;
  // HashMap：字母e->以e结尾的单词集合
  Dictionary<char, Arraylist<Node>> endLetter_to_nodes;
  
  class Node
  {
  		// 单词
  		public string word;
  		// 第一个字母s
  		public char startLetter;
  		// 最后一个字母e
  		public char endLetter;
  }
  
  Arraylist<Node> getNextNode(Node n)
  {
  		// Next边：节点n末尾字母e -> 以e开头的字母的集合
  		return startLetter_to_nodes(n.endLetter);
  }
  
  Arraylist<Node> getLastNode(Node n)
  {
  		// Last边：节点n开头字母s -> 以s结尾的字母的集合
  		return endLetter_to_nodes(n.startLetter);
  }
  

第二步 判断是否有环

Detect Cycle in a Directed Graph - GeeksforGeeks

// A C# Program to detect cycle in a graph
using System;
using System.Collections.Generic;

public class Graph {
	
	private readonly int V;
	private readonly List<List<int>> adj;

	public Graph(int V)
	{
		this.V = V;
		adj = new List<List<int>>(V);
		
		for (int i = 0; i < V; i++)
			adj.Add(new List<int>());
	}

	private bool isCyclicUtil(int i, bool[] visited, bool[] recStack)
	{
			// Mark the current node as visited and part of recursion stack
			if (recStack[i]) return true;
			if (visited[i]) return false;
			visited[i] = true;
			recStack[i] = true;
			List<int> children = adj[i];
		
			foreach (int c in children)
				if (isCyclicUtil(c, visited, recStack)) return true;
			recStack[i] = false;
			return false;
	}

	// Returns true if the graph contains a cycle, else false.
	private bool isCyclic()
	{
		bool[] visited = new bool[V];
		bool[] recStack = new bool[V];
		
		for (int i = 0; i < V; i++)
			if (isCyclicUtil(i, visited, recStack))
				return true;
		return false;
	}

第三步 解题

1. 有向无环图最长路

①无权

• -w

  （以及无环的-w -r）

  有向无权无环图最长边问题

• -w -h 和 -w -t

  指定起始点DFS（-t就用反向图getLastNode）

②加权

• -c

  有向加权无环图最长边问题

  边的权重 为边的终点的单词长度

  

• -c -h 和 -c -t

  指定起点DFS

2. 有向有环图最长路

①没有-r参数

• -w (-h) (-t)
• -c (-h) (-t)