Graph Valid Tree

LintCode Q 178 - Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Example 1:
Input: n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]] ; Output: true.

Example 2:
Input: n = 5 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] ; Output: false.

Notice: You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Solution

An undirected graph is tree if it has following properties.

1. There is no cycle.
2. The graph is connected.

How to check if a graph satisfies the above two properties?

1. If there are N nodes and N-1 edges, then the graph has no cycle. That is edges = n - 1.
2. There is no island in the graph, if and only if we can visit every node in the graph from any arbitrary node in the graph.

Solution 1 : BFS

Code:

public boolean validTree(int n, int[][] edges) {
	if (n == 0) return false;
	if (edges.length != n - 1) return false;

	Map<Integer, Set<Integer>> graph = new HashMap<>();

	// build the graph
	for (int i = 0; i < n; i++)
		graph.put(i, new HashSet<>());
	for (int[] edge: edges) {
		graph.get(edge[0]).add(edge[1]);
		graph.get(edge[1]).add(edge[0]);
	}

	Queue<Integer> que = new PriorityQueue<>();
	Set<Integer> visited = new HashSet<>();
	que.offer(0); visited.add(0);

	while (!que.isEmpty()) {
		int curr = que.poll();
		for (int next: graph.get(curr)) {
			if (visited.contains(next)) continue;
			que.offer(next);
			visited.add(next);
		}
	}

	return vistied.size() == n;
}

Solution 2 : Disjoint Set / Union Find Set

1. Build the union, if I am trying to union an existing edge, then return false;
2. Check if there is only one union in the graph.

Another way:

1. Add a count field in the UnionFindSet, denoting the number of different unions.
2. check if the count for the given graph equals 1.

Code:

class UnionFindSet {
	int[] parent;
	int[] rank;

	public UnionFindSet(int size) {
		parent = new int[size]; rank = new int[size];
		for (int i = 0; i < size; i++) 
			parent[i] = i;
	}

	public int Find (int x) {
		if (x != parent[x])
			parent[x] = Find(parent[x]);
		return parent[x];
	}

	public void Union (int x, int y) {
		int px = Find(x), py = Find(y);
		if (rank(px) > rank(py)) parent[py] = px;
		if (rank(py) > rank(px)) parent[px] = py;
		else {
			parent[py] = px;
			rank[px]++;
		}
	}
}

public boolean validTree(int n, int[][] edges) {
	if (n == 0) return false;
	if (edges.length != n - 1) return false;

	UnionFindSet ufs = new UnionFindSet();
	for (int[] edge: edges) {
		if (ufs.find(edge[0]) == ufs.find(edge[1])) return false;
		ufs.union(edge[0], edge[1]);
	}

	for (int i = 1; i < n; i++) {
		if (ufs.find(i - 1) != ufs.find(i)) return false;
	}

	return true;
}