3 图的遍历 6题

sy380: 无向图的连通块简单

https://sunnywhy.com/sfbj/10/3/380

现有一个共n个顶点、m条边的无向图（假设顶点编号为从0到n-1），求图中的连通块个数。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq \frac{n (n - 1)}{2}$ ），分别表示顶点数和边数；

接下来m行，每行两个整数u、v（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v$ ），表示一条边的两个端点的编号。数据保证不会有重边。

输出

输出一个整数，表示图中的连通块个数。

样例1

输入

输出

解释

对应的无向图如下图所示，共有两个连通块。

无向图的连通块.png

要解决这个问题，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来找出图中的所有连通块。我们首先创建一个邻接列表来表示图，然后对每个未访问的节点进行DFS或BFS，每次搜索都会找到一个连通块。搜索过程中，我们需要标记已访问的节点，以防止重复访问。

以下是使用DFS的Python代码：

python

def dfs(node, visited, adjacency_list):
    visited[node] = True
    for neighbor in adjacency_list[node]:
        if not visited[neighbor]:
            dfs(neighbor, visited, adjacency_list)

n, m = map(int, input().split())
adjacency_list = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    adjacency_list[u].append(v)
    adjacency_list[v].append(u)

visited = [False] * n
connected_components = 0
for i in range(n):
    if not visited[i]:
        dfs(i, visited, adjacency_list)
        connected_components += 1

print(connected_components)

在这段代码中，我们首先读取顶点数和边数，然后读取每条边的信息并在邻接列表中添加相应的边。然后我们初始化一个布尔数组visited来跟踪已访问的节点，并初始化连通块的数量为0。接着，我们遍历每个节点，如果它还未被访问，我们就从它开始进行DFS，并将连通块的数量加1。最后，我们输出连通块的数量。

sy381: 无向连通图简单

https://sunnywhy.com/sfbj/10/3/381

现有一个共个顶点、条边的无向图（假设顶点编号为从0到n-1），判断其是否是连通图。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq \frac{n (n - 1)}{2}$ ），分别表示顶点数和边数；

接下来m行，每行两个整数u、v（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v$ ），表示一条边的起点和终点的编号。数据保证不会有重边。

输出

如果是连通图，那么输出Yes，否则输出No。

样例1

输入

输出

No

解释

对应的无向图如下图所示，不是连通图。

无向图的连通块.png

样例2

输入

输出

Yes

解释

对应的无向图如下图所示，是连通图。

无向连通图_样例2.png

要判断一个图是否是连通图，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图。如果在遍历结束后，所有的节点都被访问过，那么这个图就是连通图。否则，就不是连通图。

以下是使用DFS的Python代码：

python

def dfs(node, visited, adjacency_list):
    visited[node] = True
    for neighbor in adjacency_list[node]:
        if not visited[neighbor]:
            dfs(neighbor, visited, adjacency_list)

n, m = map(int, input().split())
adjacency_list = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    adjacency_list[u].append(v)
    adjacency_list[v].append(u)

visited = [False] * n
dfs(0, visited, adjacency_list)

if all(visited):
    print("Yes")
else:
    print("No")

在这段代码中，我们首先读取顶点数和边数，然后读取每条边的信息并在邻接列表中添加相应的边。然后我们初始化一个布尔数组visited来跟踪已访问的节点，并从第一个节点开始进行DFS。最后，我们检查是否所有的节点都被访问过，如果是，那么输出Yes，否则输出No。

sy382: 有向图判环中等

Karn, dfs, Floyd-Warshall, https://sunnywhy.com/sfbj/10/3/382

现有一个共n个顶点、m条边的有向图（假设顶点编号为从0到n-1），如果从图中一个顶点出发，沿着图中的有向边前进，最后能回到这个顶点，那么就称其为图中的一个环。判断图中是否有环。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq n (n - 1)$ ），分别表示顶点数和边数；

接下来m行，每行两个整数u、v（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v$ ），表示一条边的起点和终点的编号。数据保证不会有重边。

输出

如果图中有环，那么输出Yes，否则输出No。

样例1

输入

输出

Yes

解释

对应的有向图如下图所示，存在0->3->2->1->0的环。

有向图判环_样例1.png

样例2

输入

输出

No

解释

对应的有向图如下图所示，图中不存在环。

有向图判环_样例2.png

在这个问题中，需要检查给定的有向图是否包含一个环。可以使用深度优先搜索（DFS）来解决这个问题。在DFS中，从一个节点开始，然后访问它的每一个邻居。如果在访问过程中，遇到了一个已经在当前路径中的节点，那么就存在一个环。可以使用一个颜色数组来跟踪每个节点的状态：未访问（0），正在访问（1），已访问（2）。

以下是解决这个问题的Python代码：

python

def has_cycle(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)

    color = [0] * n

    def dfs(node):
        if color[node] == 1:
            return True
        if color[node] == 2:
            return False

        color[node] = 1
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        color[node] = 2
        return False

    for i in range(n):
        if dfs(i):
            return "Yes"
    return "No"

# 接收数据
n, m = map(int, input().split())
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))

# 调用函数
print(has_cycle(n, edges))

在这个函数中，我们首先构建了一个邻接列表来表示图。然后，我们对每个节点执行深度优先搜索。如果在搜索过程中，我们遇到了一个正在访问的节点，那么就存在一个环。如果我们遍历完所有的节点都没有找到环，那么就返回"No"。

这个问题可以通过拓扑排序（Topological Sort）或深度优先遍历（DFS）来解决。对于有向图判环，最经典的算法是拓扑排序。

方法一：BFS（Kahn 算法/拓扑排序）

在有向图中，判定环的逻辑与无向图不同。在有向图中，BFS 如果只是简单记录是否访问过，是无法准确判环的（因为多个点指向同一个点并不代表有环，比如 A→C,B→C）。

入度统计：统计图中每个顶点的入度（即有多少条边指向该顶点）。
队列初始化：将所有入度为 0 的顶点放入一个队列中。入度为 0 意味着没有边指向它，它不可能是环的一部分。
循环处理：
- 从队列中取出一个顶点 $u$ 。
- 遍历从 $u$ 出发的所有边 $(u, v)$ 。
- 将顶点 $v$ 的入度减 1。如果 $v$ 的入度减到了 0，说明在去掉 $u$ 之后， $v$ 也没有前驱了，将其加入队列。
结果判断：
- 如果最终被移出队列的顶点数量等于图中顶点的总数 $n$ ，说明所有顶点都可以排成一个拓扑序列，图中没有环。
- 如果移出队列的顶点数量小于 $n$ ，说明剩下的顶点之间存在相互依赖关系（即存在环），输出 Yes。

Python 代码实现

python

import sys
from collections import deque

def solve():
    # 读取所有输入数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 顶点数 n, 边数 m
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 邻接表表示图
    adj = [[] for _ in range(n)]
    # 记录每个顶点的入度
    in_degree = [0] * n
    
    # 构建图
    current = 2
    for _ in range(m):
        u = int(input_data[current])
        v = int(input_data[current + 1])
        adj[u].append(v)
        in_degree[v] += 1
        current += 2
        
    # 将所有入度为 0 的顶点入队
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    
    # 记录拓扑序列中的顶点数量
    count = 0
    
    while queue:
        u = queue.popleft()
        count += 1
        
        # 遍历邻接点
        for v in adj[u]:
            in_degree[v] -= 1
            # 如果入度变为 0，入队
            if in_degree[v] == 0:
                queue.append(v)
                
    # 如果 count 等于 n，说明可以完成拓扑排序，即无环
    if count == n:
        print("No")
    else:
        print("Yes")

if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度： $O (n + m)$ ，其中 $n$ 是顶点数， $m$ 是边数。我们需要遍历所有的点和边来建立入度表，并进行一次拓扑排序。
空间复杂度： $O (n + m)$ ，用于存储邻接表和入度数组。

为什么这个方法有效？

在有向无环图（DAG）中，一定至少存在一个入度为 0 的点。当我们不断移除入度为 0 的点时，如果图中没有环，最终所有点都会被移除。如果图中存在环，环上的点其入度永远不会降为 0（因为环中的点总被环内前一个点指向），因此它们永远不会进入队列，最终处理的点数 count 就会小于 n。

方法二：DFS 染色法（三色标记法）

这是有向图判环最标准、最高效的 DFS 方法。我们将每个节点标记为三种颜色之一：

白色 (0)：尚未访问。
灰色 (1)：正在访问中（递归栈中）。如果我们在 DFS 过程中遇到了一个灰色的点，说明找到了一个后向边（Back Edge），即存在环。
黑色 (2)：已完全访问结束（该节点及其所有子孙节点都已遍历完，且没发现环）。

Python 实现：

python

import sys

# 增加递归深度限制，防止深搜溢出（虽然本题 n=100 没问题）
sys.setrecursionlimit(2000)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return
    n, m = int(input_data[0]), int(input_data[1])
    
    adj = [[] for _ in range(n)]
    idx = 2
    for _ in range(m):
        u, v = int(input_data[idx]), int(input_data[idx+1])
        adj[u].append(v)
        idx += 2

    # 状态数组：0-未访问，1-访问中，2-访问结束
    color = [0] * n

    def has_cycle_dfs(u):
        color[u] = 1  # 标记为访问中（进入递归栈）
        
        for v in adj[u]:
            if color[v] == 1:
                return True  # 发现后向边，有环
            if color[v] == 0:
                if has_cycle_dfs(v):
                    return True
        
        color[u] = 2  # 标记为访问结束（移出递归栈）
        return False

    # 遍历所有节点，防止图是不连通的
    found_cycle = False
    for i in range(n):
        if color[i] == 0:
            if has_cycle_dfs(i):
                found_cycle = True
                break
    
    print("Yes" if found_cycle else "No")

solve()

方法三：Floyd-Warshall 算法（适用于 $n$ 较小）

如果 $n$ 非常小（比如 $n \leq 100$ ），还可以使用类似 Floyd 的动态规划方法来检测。

逻辑：如果从 $u$ 出发能到达 $v$ ，且从 $v$ 出发能回到 $u$ ，或者存在 $u$ 能够到达自身（ $d i s t [i] [i]$ 为真），则有环。

python

import sys


def solve_floyd():
    input_data = sys.stdin.read().split()
    if not input_data: return
    n, m = int(input_data[0]), int(input_data[1])

    reachable = [[False] * n for _ in range(n)]
    idx = 2
    for _ in range(m):
        u, v = int(input_data[idx]), int(input_data[idx + 1])
        reachable[u][v] = True
        idx += 2

    # Floyd 传递闭包
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if reachable[i][k] and reachable[k][j]:
                    reachable[i][j] = True

    # 检查是否存在任意一点 i 满足 reachable[i][i]
    # 注意：本题要求 u != v，所以环至少由两个点或间接路径组成
    # 在执行过程中，如果 i 能到 k，k 能到 i，则 reachable[i][i] 会变 True
    has_cycle = any(reachable[i][i] for i in range(n))

    print("Yes" if has_cycle else "No")


solve_floyd()

注：这种方法复杂度为 $O (n^{3})$ ，本题 $n = 100$ 勉强可以用，但不如 DFS/拓扑排序高效。

总结比较

方法	复杂度	推荐场景
拓扑排序 (BFS)	$O (n + m)$	最常用，逻辑清晰，且能顺便求出拓扑序列。
染色法 (DFS)	$O (n + m)$	递归实现简单，在寻找特定环路径时很有用。
Floyd (DP)	$O (n^{3})$	仅在 $n$ 极小且需要求全图连通性时考虑。

对于本题，拓扑排序（Kahn's BFS）和染色法（DFS）是最佳选择。

sy383: 最大权值连通块中等

https://sunnywhy.com/sfbj/10/3/383

现有一个共个顶点、条边的无向图（假设顶点编号为从0到n-1），每个顶点有各自的权值。我们把一个连通块中所有顶点的权值之和称为这个连通块的权值。求图中所有连通块的最大权值。

输入

第一行两个整数n、m（ $1 \leq n \leq 100, 0 \leq m \leq \frac{n (n - 1)}{2}$ ），分别表示顶点数和边数；

第二行个用空格隔开的正整数（每个正整数不超过100），表示个顶点的权值。

接下来m行，每行两个整数u、v（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v$ ），表示一条边的起点和终点的编号。数据保证不会有重边。

输出

输出一个整数，表示连通块的最大权值。

样例1

输入

6 5
2 3 4 1 3 2
0 1
0 3
3 5
2 4
1 5

输出

解释

对应的无向图如下图所示，左边连通块的权值为，右边连通块的权值为，因此最大权值为8。

最大权值连通块.png

提供三种解法：常规，类，并查集（类似最小生成树的Krusal算法）

需要找到给定无向图中所有连通块的最大权值。使用深度优先搜索（DFS）来解决这个问题。在DFS中，从一个节点开始，然后访问它的每一个邻居。可以使用一个visited数组来跟踪每个节点是否已经被访问过。对于每个连通块，可以计算其权值之和，并更新最大权值。

以下是解决这个问题的Python代码：

python

def max_weight(n, m, weights, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * n
    max_weight = 0

    def dfs(node):
        visited[node] = True
        total_weight = weights[node]
        for neighbor in graph[node]:
            if not visited[neighbor]:
                total_weight += dfs(neighbor)
        return total_weight

    for i in range(n):
        if not visited[i]:
            max_weight = max(max_weight, dfs(i))

    return max_weight

# 接收数据
n, m = map(int, input().split())
weights = list(map(int, input().split()))
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))

# 调用函数
print(max_weight(n, m, weights, edges))

在这段代码中，首先通过input()函数接收用户输入的顶点数n、边数m和每个顶点的权值，然后在一个循环中接收每条边的起点和终点，并将它们添加到edges列表中。然后，我们调用max_weight函数并打印结果。

类的写法

python

#洪亮 物理学院
class Vertex:
    def __init__(self,key,weight):
        self.key=key
        self.weight=weight
        self.nbrs=[]
    def addnbr(self,nbr):
        self.nbrs.append(nbr)
        
class Graph:
    def __init__(self):
        self.vertexs={}
    def addvertex(self,key,weight):
        cur=Vertex(key,weight)
        self.vertexs[key]=cur
        return cur
    def addedge(self,k1,k2):
        self.vertexs[k1].nbrs.append(self.vertexs[k2])
        self.vertexs[k2].nbrs.append(self.vertexs[k1])
        
def DFS(vertex):
    ans=vertex.weight
    check[vertex.key]=False
    for k in vertex.nbrs:
        if check[k.key]:
            ans+=DFS(k)
            check[k.key]=False
    return ans

n,m=map(int,input().split())
check=[True]*n
weights=list(map(int,input().split()))
p=Graph()
for i in range(n):
    p.addvertex(i,weights[i])
for j in range(m):
    k1,k2=map(int,input().split())
    p.addedge(k1,k2)
ans=0
for vertex in p.vertexs.values():
    if check[vertex.key]:
        ans=max(ans,DFS(vertex))
print(ans)

学习了图的相关知识，发现用并查集处理连通分支相关问题好像很方便，可以简化很多代码。

用并查集存储连通关系，额外对并查集每个根节点维护一个所在集合权值和，union时把新根的s变为原来两个根之和即可。

python

# 杨博文，数学科学学院
n, m = map(int, input().split())
key = list(map(int, input().split()))
s = [key[i] for i in range(n)]
p = [i for i in range(n)]


def find(x):
    if p[x] == x:
        return x
    else:
        y = find(p[x])
        p[x] = y
        return y


def union(x, y):
    u = find(x);
    v = find(y)
    if u != v:
        p[u] = v;
        s[v] += s[u]


for _ in range(m):
    x, y = map(int, input().split())
    union(x, y)
print(max(s))

python

# 余汶青 生命科学学院
import sys
from collections import deque

class Vertex:
    def __init__(self,key,weight=0):
        self.id=key
        self.weight=weight
        self.connectedTo={}
        self.visit=0
    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr]=weight
    def __str__(self):
        return str(self.id)+'connectedTo:'+str([x.id for x in self.connectedTo])
    def getConnections(self):
        return self.connectedTo.keys()
    def getId(self):
        return self.id
    def getWeight(self,nbr):
        return self.connectedTo[nbr]
class Graph:
    def __init__(self):
        self.vertList={}
        self.numVertices=0
    def addVertex(self,key,weight=0):
        self.numVertices+=1
        newVertex=Vertex(key,weight)
        self.vertList[key]=newVertex
        return newVertex
    def getVertex(self,n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None
    def __contains__(self,n):
        return n in self.vertList
    def addEdge(self,f,t,weight=0):
        if f not in self.vertList:
            nv=self.addVertex(f)
        if t not in self.vertList:
            nv=self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t],weight)
    def getVertices(self):
        return self.vertList.keys()
    def __iter__(self):
        return iter(self.vertList.values())
    
def bfs(seed):
    ans=0
    q=deque()
    q.append(seed)
    ans+=seed.weight
    
    seed.visit=1
    while q:
        a=q.popleft()
        for i in a.getConnections():
            if i.visit==0:
                q.append(i)
                ans+=i.weight
                i.visit=1
    return ans
    
    
graph=Graph()
n,m=map(int,input().split())
weight=[int(i) for i in input().split()]
for i in range(n):
    graph.addVertex(i,weight[i])
for i in range(m):
    a,b=map(int,input().split())
    graph.addEdge(a, b)
    graph.addEdge(b, a)
ans=0
for i in graph.getVertices():
    vex=graph.getVertex(i)
    if vex.visit==0:
        ans=max(ans,bfs(vex))
print(ans)

sy384: 无向图的顶点层号

https://sunnywhy.com/sfbj/10/3/384

现有一个共n个顶点、m条边的无向连通图（假设顶点编号为从0到n-1）。我们称从s号顶点出发到达其他顶点经过的最小边数称为各顶点的层号。求图中所有顶点的层号。

输入

第一行三个整数n、m、s（ $1 \leq n \leq 100, 0 \leq m \leq \frac{n (n - 1)}{2}, 0 \leq s \leq n - 1$ ），分别表示顶点数、边数、起始顶点编号；

接下来m行，每行两个整数u、v（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v$ ），表示一条边的起点和终点的编号。数据保证不会有重边。

输出

输出n个整数，分别为编号从0到n-1的顶点的层号。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

输出

0 1 3 1 2 2

解释

对应的无向图和顶点层号如下图所示。

无向图的顶点层号.png

需要找到从给定的起始顶点到图中所有其他顶点的最短路径长度，这也被称为顶点的层号。可以使用广度优先搜索（BFS）来解决这个问题。在BFS中，从起始节点开始，然后访问它的所有邻居，然后再访问这些邻居的邻居，依此类推。我们可以使用一个队列来跟踪待访问的节点，并使用一个距离数组来记录从起始节点到每个节点的最短距离。

以下是解决这个问题的Python代码：

python

from collections import deque

def bfs(n, m, s, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    distance = [-1] * n
    distance[s] = 0

    queue = deque([s])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)

    return distance

# 接收数据
n, m, s = map(int, input().split())
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))

# 调用函数
distances = bfs(n, m, s, edges)
print(' '.join(map(str, distances)))

在这段代码中，我们首先通过input()函数接收用户输入的顶点数n、边数m和起始顶点s，然后在一个循环中接收每条边的起点和终点，并将它们添加到edges列表中。然后，我们调用bfs函数并打印结果。

sy385: 受限层号的顶点数中等

https://sunnywhy.com/sfbj/10/3/385

现有一个共n个顶点、m条边的有向图（假设顶点编号为从0到n-1）。我们称从s号顶点出发到达其他顶点经过的最小边数称为各顶点的层号。求层号不超过的顶点个数。

输入

第一行四个整数n、m、s、k（ $1 \leq n \leq 100, 0 \leq m \leq \frac{n (n - 1)}{2}, 0 \leq s \leq n - 1, 0 \leq k \leq 100$ ），分别表示顶点数、边数、起始顶点编号、层号上限；

接下来m行，每行两个整数u、v（ $0 \leq u \leq n - 1, 0 \leq v \leq n - 1, u \neq v$ ），表示一条边的起点和终点的编号。数据保证不会有重边。

输出

输出一个整数，表示层号不超过的顶点个数。

样例1

输入

输出

解释

对应的有向图和顶点层号如下图所示，层号不超过2的顶点有5个。

受限层号的顶点数.png

需要找到从给定的起始顶点到图中所有其他顶点的最短路径长度（也被称为顶点的层号），并计算层号不超过k的顶点个数。可以使用广度优先搜索（BFS）来解决这个问题。在BFS中，从起始节点开始，然后访问它的所有邻居，然后再访问这些邻居的邻居，依此类推。可以使用一个队列来跟踪待访问的节点，并使用一个距离数组来记录从起始节点到每个节点的最短距离。

以下是解决这个问题的Python代码：

python

from collections import deque

def bfs(n, m, s, k, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)  # 只按照输入的方向添加边

    distance = [-1] * n
    distance[s] = 0

    queue = deque([s])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)

    return sum(1 for d in distance if d <= k and d != -1)

# 接收数据
n, m, s, k = map(int, input().split())
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))

# 调用函数
count = bfs(n, m, s, k, edges)
print(count)

在这段代码中，首先通过input()函数接收用户输入的顶点数n、边数m、起始顶点s和层号上限k，然后在一个循环中接收每条边的起点和终点，并将它们添加到edges列表中。然后，调用bfs函数并打印结果。

3 图的遍历 6题 ​

sy380: 无向图的连通块 简单 ​

sy381: 无向连通图 简单 ​

sy382: 有向图判环 中等 ​

方法一：BFS（Kahn 算法/拓扑排序） ​

方法二：DFS 染色法（三色标记法） ​

方法三：Floyd-Warshall 算法（适用于 n 较小） ​

总结比较 ​

sy383: 最大权值连通块 中等 ​

sy384: 无向图的顶点层号 ​

sy385: 受限层号的顶点数 中等 ​

3 图的遍历 6题

sy380: 无向图的连通块简单

sy381: 无向连通图简单

sy382: 有向图判环中等

方法一：BFS（Kahn 算法/拓扑排序）

方法二：DFS 染色法（三色标记法）

方法三：Floyd-Warshall 算法（适用于 $n$ 较小）

总结比较

sy383: 最大权值连通块中等

sy384: 无向图的顶点层号

sy385: 受限层号的顶点数中等