代码随想录 1971.寻找图中是否存在路径

方法一：并查集

class Solution { private int[] p; public boolean validPath(int n, int[][] edges, int source, int destination) { p = new int[n]; for(int i = 0;i < n;i++){ p[i] = i; } for(int[] e : edges){ p[find(e[0])] = find(e[1]); } return find(source) == find(destination); } private int find(int x){ if(p[x] != x){ //如果根不是自己（x） p[x] = find(p[x]); //根据数组下标一层一层向下找 } return p[x]; //返回根 } }

方法二：暴力BFS

class Solution { public boolean validPath(int n, int[][] edges, int source, int destination) { boolean[] used = new boolean[n]; //used[i] = true表示从source可以到达节点i used[source] = true; //起始节点默认可达 boolean newUsedFound = true; //标记本轮循环是否发现了新的可达节点 while(!used[destination] && newUsedFound){ //只要目标节点还未被访问并且还能发现新节点，就继续循环 newUsedFound = false; for(int i = edges.length - 1;i >= 0;i--){ //从后往前遍历类似于反向BFS,避免超时 //每次循环扫描所有边 if(used[edges[i][0]]){ //如果u可达v不可达，标记v可达 if(!used[edges[i][1]]){ newUsedFound = used[edges[i][1]] = true; } } else if(used[edges[i][1]]){ //如果v可达u不可达，标记u可达 newUsedFound = used[edges[i][0]] = true; } if(used[destination]){ //找到目标节点，提前结束 break; } } } return used[destination]; } }