261. Graph Valid Tree

Leetcode Graph Depth-first Search Breath-first Search Union Find

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.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

1. Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
2. According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

分析

LeetCode这道题目需要收费，参见LintCode。

A tree is an acyclic connected graph.

判断无向图是否为树。图论基本算法。图为树的先决条件是1.无环，2.可连通。判断无向图有环的方法有bfs、dfs、并查集，判断可连接的方法还是有bfs、dfs、并查集。 无向图的环的判断可参考这里。

使用并查集(weighted-path with compression)：

/**
 * @param n: An integer
 * @param edges: a list of undirected edges
 * @return: true if it's a valid tree, or false
 */
public boolean validTree(int n, int[][] edges) {
    // special case, 0 vertex
    if (n == 0) return false;
    int [] id = new int[n];
    int [] size = new int[n];

    // 初始化id
    for (int i = 0; i < n; i++)
        id[i] = i;

    // 确认图是否有环
    for (int[] edge : edges) {
        int v = edge[0], w = edge[1];
        // 遍历所有边，查找到边的顶点所在的集合，如果相同，则有环
        int i = find(id, v), j = find(id, w);
        if (i == j) return false;
        union(id, size, i, j);
    }

    // 确认图是否连通
    int group = find(id, 0);
    for (int v = 1; v < n; v++)
        if (find(id, v) != group) return false;

    return true;
}

// union v and w
private void union(int[] id, int[] size, int v, int w) {
    // find roots of v and w
    int i = find(id, v);
    int j = find(id, w);
    if (i == j) return;
    // link the root of small tree to large tree
    if (size[i] > size[j]) {id[j] = i; size[i] += size[j];}
    else {id[i] = j; size[j] += size[i];}
}

private int find(int[] id, int v) {
    while (id[v] != v) {
        // point to its grandparent;
        id[v] = id[id[v]];
        v = id[v];
    }
    return v;
}

并查集的方案是最快的，beat 100%。因为使用DFS和BFS需要构建图。