261. Graph Valid Tree --【M】Google / Facebook / Zenefits / DFS / BFS / Gragh / Union Find

https://leetcode.com/problems/graph-valid-tree/

小土刀 union find

https://mnmunknown.gitbooks.io/algorithm-notes/content/67,_union-find,_bing_cha_ji_ying_yong.html

3ms 50%

public class Solution {

class UF {

private int[] id, size;

private int count;

private boolean hasCycle;

public UF(int n) {

id = new int[n];

size = new int[n];

count = n;

for (int i = 0; i < n; i++) {

id[i] = i;

size[i] = 1;

}

}

public int getCount() {

return this.count;

}

public int find(int p) {

while (p != id[p]) {

id[p] = id[id[p]];

p = id[p];

}

return p;

}

public boolean connected(int p, int q) {

return find(p) == find(q);

}

public void union(int p, int q) {

Integer a = find(p);

Integer b = find(q);

if (a == null || b == null)

return;

if (a.equals(b)) {

hasCycle = true;

return;

}

if (size[a] > size[b]) {

id[b] = a;

size[a] += size[b];

}

else {

id[a] = b;

size[a] += size[b];

}

count--;

}

public boolean isTree() {

return (!hasCycle && getCount() == 1);

}

}

public boolean validTree(int n, int[][] edges) {

if (n <= 1)

return true;

UF uf = new UF(n);

for (int[] edge : edges) {

if (uf.hasCycle == true)

return false;

uf.union(edge[0], edge[1]);

}

return uf.isTree();

}

}

**总结：

本质；已知N个node以及int[][] edges判断是否能形成tree。思路：是否是tree条件，一是无环，二是单个root节点也即connected component只有一个。union find方法：class UF里多一个hasCycle的变量。遍历edges, 判断有无环，没有的话，union，最后返回isTree() 即为所求。