Find if Path Exists in Graph
给一个无环双向图, 找是否有一个path.
这题就union find的模板题.
|
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 |
class Solution { class DSU{ int[] p; public DSU(int size) { this.p = new int[size]; for(int i = 0; i < size; i++) { p[i] = i; } } int get(int v) { if(p[v] == v) return v; return p[v] = get(p[v]); } boolean union(int a, int b) { a = get(a); b = get(b); if(a == b) return false; p[a] = b; return true; } } public boolean validPath(int n, int[][] edges, int start, int end) { if(edges == null || edges.length == 0) if(n == 1 && start == 0 && end == 0) return true; else return false; DSU dsu = new DSU(n); for(int[] e : edges) dsu.union(e[0],e[1]); return dsu.get(start) == dsu.get(end); } } |