05 August 2008
有向图中判断两个点之间是否有path
BFS - O(V + E)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public boolean validPath(int n, int[][] edges, int start, int end) {
boolean[] visited = new boolean[n];
HashSet<Integer>[] graph = new HashSet[n];
int i, j;
for(i = 0; i < n; i++){
graph[i] = new HashSet<Integer>();
}
for(int[] edge : edges){
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
if(graph[start].contains(end)){ // direct connection exists
return true;
}
}
Queue<Integer> queue = new LinkedList<Integer>();
int N, current;
queue.offer(start);
visited[start] = true;
while(!queue.isEmpty()){
N = queue.size();
for(i = 0; i < N; i++){
current = queue.poll();
if(current == end){
return true;
}
for(Integer neighbor : graph[current]){
if(!visited[neighbor]){
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
return false;
}
}
DFS - O(V + E)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private boolean seen;
public boolean validPath(int n, int[][] edges, int start, int end) {
boolean[] visited = new boolean[n];
HashSet<Integer>[] graph = new HashSet[n];
int i, j;
for(i = 0; i < n; i++){
graph[i] = new HashSet<Integer>();
}
for(int[] edge : edges){
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
if(graph[start].contains(end)){ // direct connection exists
return true;
}
}
seen = false;
dfs(graph, visited, start, end);
return seen;
}
private void dfs(HashSet<Integer>[] graph, boolean[] visited, int start, int end){
if(!visited[start] && !seen){
if(start == end){
seen = true;
return;
}
visited[start] = true;
for(Integer neighbor : graph[start]){
dfs(graph, visited, neighbor, end);
}
}
}
}
Disjoint Set Union by Rank - O(E alpha(V)) + O(alpha(V))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class DisjointSetUnion{
private int[] parent;
private int[] rank;
private int N;
public DisjointSetUnion(int n){
this.N = n;
this.parent = new int[this.N];
this.rank = new int[this.N];
for(int i = 0; i < this.N; i++){
this.parent[i] = i;
this.rank[i] = 1;
}
}
public boolean areConnected(int u, int v){
return find(u) == find(v);
}
public void union(int u, int v){
if(u != v){
int a = find(u);
int b = find(v);
if(a != b){
if(rank[a] > rank[b]){
parent[b] = a;
rank[a] += rank[b];
}else{
parent[a] = b;
rank[b] += rank[a];
}
}
}
}
private int find(int u){
int x = u;
while(x != this.parent[x]){
x = this.parent[x];
}
this.parent[u] = x;
return x;
}
}
class Solution {
public boolean validPath(int n, int[][] edges, int start, int end) {
DisjointSetUnion set = new DisjointSetUnion(n);
for(int[] edge : edges){
set.union(edge[0], edge[1]);
}
return set.areConnected(start, end);
}
}