如何计算无向图中包含孤立节点的不相交树的数量？

你搜索不到对应解决方案是因为关键词不准确，该问题属于图论经典基础问题，本质是无向图连通分量计数。你自定义的「不相交树」和图论标准的无环连通树定义不同，实际你要统计的是无向图所有连通分量（包含带环的连通分量、孤立节点），直接用连通分量计数的标准解法即可。

解法1：DFS/BFS 遍历法 #

思路 #

1. 为所有节点标记为未访问状态
2. 遍历每个节点，若节点未被访问过，则从该节点出发做DFS/BFS遍历，将所有可达节点标记为已访问
3. 每触发一次新的DFS/BFS遍历，说明找到一个新的连通分量，计数加1
4. 最终的计数值就是你需要的不相交树数量

代码示例（Python） #

nodes = [1,2,3,4,5,6,7,8,9]
edges = [(2,3), (2,7), (3,7), (4,3), (5,1), (5,6)]

# 构建邻接表
adj = {node: [] for node in nodes}
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

visited = set()
count = 0

for node in nodes:
    if node not in visited:
        count += 1
        # BFS遍历当前连通分量所有节点
        q = [node]
        visited.add(node)
        while q:
            cur = q.pop(0)
            for neighbor in adj[cur]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)

print(count) # 输出结果为3，和示例匹配

解法2：并查集（Union-Find）法 #

适合节点和边的规模较大的场景，时间效率更高。

思路 #

1. 初始化并查集，每个节点的父节点指向自己，初始连通分量数等于节点总数
2. 遍历每一条边，对边的两个节点执行合并操作：如果两个节点原本不属于同一个集合，合并成功后连通分量数减1
3. 所有边处理完成后，剩余的连通分量数就是你需要的结果

代码示例（Python） #

class UnionFind:
    def __init__(self, nodes):
        self.parent = {node: node for node in nodes}
        self.count = len(nodes) # 初始连通分量数等于节点总数
    
    def find(self, x):
        # 路径压缩优化
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return # 两个节点已经在同一个集合，无需合并
        self.parent[y_root] = x_root
        self.count -= 1 # 合并成功，连通分量数减1


# 测试示例
nodes = [1,2,3,4,5,6,7,8,9]
edges = [(2,3), (2,7), (3,7), (4,3), (5,1), (5,6)]

uf = UnionFind(nodes)
for u, v in edges:
    uf.union(u, v)

print(uf.count) # 输出结果为3，和示例匹配

内容的提问来源于stack exchange，提问作者GoCurry