LeetCode 1059. 从始点到终点的所有路径（回溯）

输入：n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
输出：false
说明：节点 1 和节点 2 都可以到达，但也会卡在那里。

输入：n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
输出：false
说明：有两种可能：在节点 3 处结束，或是在节点 1 和节点 2 之间无限循环。

输入：n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
输出：true

输入：n = 3, edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2
输出：false
说明：从始点出发的所有路径都在目标终点结束，
但存在无限多的路径，如 0-1-2，0-1-1-2，0-1-1-1-2，0-1-1-1-1-2 等。

输入：n = 2, edges = [[0,1],[1,1]], source = 0, destination = 1
输出：false
说明：在目标节点上存在无限的自环。
 
提示：
给定的图中可能带有自环和平行边。
图中的节点数 n 介于 1 和 10000 之间。
图中的边数在 0 到 10000 之间。
0 <= edges.length <= 10000
edges[i].length == 2
0 <= source <= n - 1
0 <= destination <= n - 1

class Solution {
public:
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
    	vector<bool> visited(n, false);
    	vector<vector<int>> m(n);
    	for(auto& e : edges)
    		m[e[0]].push_back(e[1]);
    	if(!m[destination].empty())
    		return false;//终点后面还有路径
		return dfs(m,visited,source,destination);
    }
    bool dfs(vector<vector<int>>& m, vector<bool>& visited, int cur, int destination) 
    {
    	if(m[cur].size()==0 && cur != destination)
    		return false;//到达一个终点，但不是目标点
    	for(int next : m[cur])//往下走
    	{
    		if(visited[next])//访问过了
    			return false;//有环
    		visited[next] = true;//访问
    		if(!dfs(m, visited, next, destination))
    			return false;
    		visited[next] = false;//回溯
    	}
        return true;
    }
};