0059.判断是否是树.md

59.判断是否是树

题目链接

C

C++

并查集做法

#include <iostream>

using namespace std;

const int N = 1010;
int p[N];

// 查询祖先节点
int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) p[i] = i;
    for (int i = 1; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if (pa == pb)
        {
            cout << "false" << endl;
            return 0;
        }
        p[pa] = pb;
    }
    cout << "true" << endl;
    return 0;
}

Java

import java.util.Scanner;

class UnionFind {
    private int[] parent;

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

    public int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);  // 路径压缩
    }

    public void union(int x, int y) {
        int u = find(x);
        int v = find(y);
        if (u != v) {
            parent[v] = u;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        UnionFind unionFind = new UnionFind(n);

        for (int i = 0; i < n - 1; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            if (unionFind.find(start) == unionFind.find(end)) {
                System.out.println("false");  // 有环
                return;
            }
            unionFind.union(start, end);
        }

        int rootCount = 0;
        for (int i = 0; i < n; i++) {
            if (unionFind.find(i) == i) {
                rootCount++;
            }
        }

        boolean isTree = rootCount == 1;
        System.out.println(isTree);
    }
}

Python

JS

Go

并查集做法

package main

import "fmt"

func main(){
    
    var n int
    fmt.Scan(&n)
    p := make([]int, n)
    for i := 0; i < n; i ++ {
        p[i] = i
    }
    
    // 路径压缩的并查集
    var find func(int) int 
    find = func(x int) int {
        if x != p[x]{
            p[x] = find(p[x])
        }
        return p[x]
    }
    for i := 1; i < n; i ++{
        var a, b int
        fmt.Scan(&a, &b)
        // 找到a、b的祖先节点
        pa, pb := find(a), find(b)
        // 判断祖先节点是否相等，若相等则说明它们之前已经是在一棵树里面了
        // 再次加边则会破坏树结构
        if pa == pb{
            fmt.Println("false")
            return
        }
        // 合并a、b所在的两个集合
        p[pa] = pb
    }
    fmt.Println("true")
}