//
// Created by 高森森 on 2022/1/29.
//

#ifndef LEETCODE_SOLUTION13_H
#define LEETCODE_SOLUTION13_H
#include <iostream>
#include <vector>
#include <queue>
#include<unordered_map>
using namespace std;

class Solution13 {
public:
    unordered_map<int ,vector<int>>map;
    vector<bool>visited;
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        //创建邻接表
        unordered_map<int ,vector<int>>map(n);
        for(vector<int> &vec:graph){
            map[vec[0]].push_back(vec[1]);
        }
        vector<bool>visited(n, false);
        if(start==target)
            return true;
        queue<int> que;
        que.push(start);
        visited[start]= true;
        while(!que.empty()){
            int node=que.front();
            que.pop();
            if(node==target)
                return true;
            visited[node]=true;
            for(int neigh:map[node]){
                if(!visited[neigh])
                    que.push(neigh);
            }
        }
        return false;
    }
    bool dfs(int start,int target){
        if(visited[start]== true)
            return false;
        if(start==target)
            return true;
        for(int neigh:map[start])
        {
           if(dfs(neigh,target))
               return true;
        }
        return false;
    }
    bool findWhetherExistsPath2(int n, vector<vector<int>>& graph, int start, int target) {
        if(start==target)
            return true;
        for(vector<int> &vec:graph){
            map[vec[0]].push_back(vec[1]);
        }
        visited.assign(n, false);
        return dfs(start,target);
    }
};


#endif //LEETCODE_SOLUTION13_H