阅读量:0
目录
1.1.4 链式前向星（Chain Forward Star）
2.2 UVA572、UVA1599、POJ2488、POJ3278
2.2.3 POJ2488 - A Knight’s Journey
2.2.4 POJ3278 - Catch That Cow
3.1.2 割点（Cut Vertex / Articulation Point）
3.1.3连通分量（Connected Component）
3.3 POJ1144、POJ3352、POJ2553、POJ1236
3.3.1 POJ1144 - Network Connections
3.3.2 POJ3352 - Road Construction
3.3.3 POJ2553 - Most Popular Element
3.3.4 POJ1236 - Network of Schools
1.图的存储
1.1 邻接矩阵、边集数组、邻接表、链式前向星
1. 1.1 邻接矩阵（Adjacency Matrix）
邻接矩阵是一种表示图的方式，使用一个二维数组。对于一个包含 n 个顶点的图，其邻接矩阵是一个 n×n 的二维数组 A，其中 A[i][j]表示顶点 i 到顶点 j 之间的边。
- 无向图：如果顶点 i和顶点 j 之间有边，则 A[i][j]=A[j][i]=1，否则为 0。
- 有向图：如果从顶点 i到顶点 j 之间有边，则 A[i][j]=1，否则为 0。
- 特点：邻接矩阵占用 O(n的平方) 的空间，对于稠密图（边接近 n的平方 条）比较合适。
优点：
- 实现简单，直观。
- 可以快速判断两个顶点之间是否有边（直接访问矩阵对应位置）。
缺点：
- 对于稀疏图（边数远少于顶点数的平方的图），空间利用率低。
- 矩阵的大小与顶点数目的平方成正比，可能浪费大量空间。
1.1.2 边集数组（Edge List）
边集数组是一种用边的集合表示图的方法。对于一个图，可以用一个边的列表来表示图中的所有边。
- 无向图：每条边用一个无序对 (u,v) 表示。
- 有向图：每条边用一个有序对 (u,v) 表示，其中 u 是起点，v 是终点。
- 特点：边集数组占用的空间是 O(E)，其中 E是边的数量，适用于稀疏图（边的数量远少于顶点数平方 ）。
优点：
- 节省空间，特别适合表示稀疏图。
缺点：
- 查找两个顶点之间是否存在边需要遍历整个数组，效率低下。
- 难以直接进行图的其他操作，如计算顶点的度等。
1.1.3 邻接表（Adjacency List）
邻接表是图的一种链式存储结构。对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图则是以顶点vi为尾的弧）。这个单链表就称为顶点vi的邻接表。
- 无向图：每个顶点都有一个链表，链表中存储与该顶点相连的所有顶点。
- 有向图：每个顶点都有一个链表，链表中存储从该顶点出发的所有边的终点。
- 特点：邻接表占用的空间是 O(V+E)，其中 V 是顶点的数量，E 是边的数量，非常适合稀疏图。
优点：
- 节省空间，特别适合表示稀疏图。
- 查找某个顶点的所有邻接点（即出边或入边）方便，时间复杂度为O(V+E)。
缺点：
- 相对于邻接矩阵，实现稍微复杂一些。
- 难以快速判断两个顶点之间是否有边（需要遍历整个邻接表）。
1.1.4 链式前向星（Chain Forward Star）
链式前向星是一种表示图的优化数据结构，特别适用于多次动态更新和查询的场景。它通过数组和链表的结合高效地存储和处理图。
- 存储结构：
head[u]：存储顶点 u的第一条边在边数组中的索引。to[e]：存储第 e条边的终点。next[e]：存储第 e 条边的下一条边在边数组中的索引。
- 操作：使用
add_edge(u, v)添加边时，更新to和next数组，以及head数组。 - 特点：链式前向星占用的空间是 O(V+E)，其中 V是顶点的数量，E 是边的数量，非常适合高效地进行图的动态更新和查询。相对于普通的邻接表，链式前向星通过结构体数组和头指针数组的结合，实现了对边的快速遍历和添加。适用于边数较多的情况，特别是需要频繁访问边信息的场景。
链式前向星的具体实现方式可能会根据具体需求有所不同，但基本思想是利用结构体数组来存储边的信息（如起点、终点、权重等），并通过头指针数组来快速定位某个顶点的所有邻接边。
1.1.5 总结
- 邻接矩阵：适合稠密图，占用空间大。
- 边集数组：适合稀疏图，结构简单。
- 邻接表：适合稀疏图，空间效率高。
- 链式前向星：适合频繁动态操作，查询和更新高效。
1.2 P3916、UVA11175、POJ3275
1. 2.1 P3916 解析与代码示例
题目解析
P3916 是一道关于图论的题目，通常会涉及最短路径、最小生成树或者其他图论算法。假设它是一道最短路径问题，我们可以用 Dijkstra 或者 Floyd-Warshall 算法来解决。
代码示例
假设题目是求单源最短路径，我们用 Dijkstra 算法来实现。
Python代码示例：
import heapq def dijkstra(graph, start): n = len(graph) dist = [float('inf')] * n dist[start] = 0 priority_queue = [(0, start)] while priority_queue: current_dist, u = heapq.heappop(priority_queue) if current_dist > dist[u]: continue for v, weight in graph[u]: distance = current_dist + weight if distance < dist[v]: dist[v] = distance heapq.heappush(priority_queue, (distance, v)) return dist # 示例图 graph = { 0: [(1, 2), (2, 4)], 1: [(2, 1)], 2: [(3, 1)], 3: [] } start = 0 print(dijkstra(graph, start))
1.2.2 UVA11175 解析与代码示例
题目解析
UVA11175 通常是涉及数论或者组合数学的题目。例如，求排列组合中的某种特定性质。
代码示例
假设题目是计算组合数 C(n, k)，我们可以用递归和动态规划来实现。
Python代码示例：
def combination(n, k): if k > n: return 0 if k == 0 or k == n: return 1 dp = [[0 for _ in range(k+1)] for _ in range(n+1)] for i in range(n+1): dp[i][0] = 1 for i in range(1, n+1): for j in range(1, min(i, k)+1): dp[i][j] = dp[i-1][j-1] + dp[i-1][j] return dp[n][k] n, k = 5, 2 print(combination(n, k))
1.2.3 POJ3275 解析与代码示例
题目解析
POJ3275 可能涉及字符串匹配或者动态规划的问题。例如，最长公共子序列 (LCS)。
代码示例
假设题目是求两个字符串的最长公共子序列，我们用动态规划来实现。
Python代码示例：
def lcs(X, Y): m = len(X) n = len(Y) dp = [[0] * (n + 1) for i in range(m + 1)] for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: dp[i][j] = 0 elif X[i-1] == Y[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[m][n] X = "AGGTAB" Y = "GXTXAYB" print("Length of LCS is", lcs(X, Y))
2.图的遍历
2.1 广度优先遍历、深度优先遍历
2.1.1 广度优先遍历（BFS）
概念
BFS 是一种层次遍历方法，从起始节点开始，逐层向外扩展。它使用队列来实现，适用于寻找最短路径等问题。
实现步骤
- 初始化一个队列，将起始节点加入队列。
- 标记起始节点为已访问。
- 重复以下步骤直到队列为空：
- 从队列中取出一个节点。
- 访问该节点的所有未被访问过的邻居节点，将它们标记为已访问，并加入队列。
示例代码
python
from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: node = queue.popleft() print(node, end=" ") for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # 示例图 graph = { 0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2] } bfs(graph, 0) 2.1.2 深度优先遍历（DFS）
概念
DFS 是一种深入遍历方法，从起始节点开始，一直深入到没有未访问的邻居节点为止，然后回溯继续访问其他未访问的节点。它使用栈来实现，递归方法本质上也使用了系统栈。
实现步骤
- 初始化一个栈，将起始节点压入栈。
- 标记起始节点为已访问。
- 重复以下步骤直到栈为空：
- 从栈中取出一个节点。
- 访问该节点的所有未被访问过的邻居节点，将它们标记为已访问，并压入栈。
示例代码
（使用显式栈）
def dfs(graph, start): visited = set() stack = [start] while stack: node = stack.pop() if node not in visited: print(node, end=" ") visited.add(node) for neighbor in graph[node]: if neighbor not in visited: stack.append(neighbor) # 示例图 graph = { 0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2] } dfs(graph, 0) （使用递归）
def dfs_recursive(graph, node, visited=None): if visited is None: visited = set() if node not in visited: print(node, end=" ") visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs_recursive(graph, neighbor, visited) # 示例图 graph = { 0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2] } dfs_recursive(graph, 0) 2.1.3 总结
- 广度优先遍历（BFS）：适合用于寻找无权图中的最短路径，使用队列实现。
- 深度优先遍历（DFS）：适合用于遍历所有可能的路径，使用栈实现（显式栈或递归）。
2.2 UVA572、UVA1599、POJ2488、POJ3278
2.2.1 UVA572 - Oil Deposits
题目解析
题目要求在一个二维网格中找到所有的油田（连通的 '@' 区域）。这可以看作是一个连通区域计数的问题，可以使用DFS或BFS进行连通分量的计数。
代码示例（使用DFS）
python
def dfs(grid, x, y, visited): stack = [(x, y)] directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)] while stack: cx, cy = stack.pop() for dx, dy in directions: nx, ny = cx + dx, cy + dy if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == '@' and not visited[nx][ny]: visited[nx][ny] = True stack.append((nx, ny)) def count_oil_deposits(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) visited = [[False for _ in range(n)] for _ in range(m)] count = 0 for i in range(m): for j in range(n): if grid[i][j] == '@' and not visited[i][j]: visited[i][j] = True dfs(grid, i, j, visited) count += 1 return count while True: m, n = map(int, input().split()) if m == 0 and n == 0: break grid = [input().strip() for _ in range(m)] print(count_oil_deposits(grid)) 2.2.2 UVA1599 - Ideal Path
题目解析
题目要求在一个无向图中找到从起点到终点的字典序最小的最短路径。可以通过BFS找到所有最短路径，再找字典序最小的路径。
代码示例
python
from collections import deque, defaultdict def ideal_path(n, m, edges, start, end): graph = defaultdict(list) for u, v, c in edges: graph[u].append((v, c)) graph[v].append((u, c)) dist = [-1] * (n + 1) dist[start] = 0 queue = deque([start]) while queue: u = queue.popleft() for v, _ in graph[u]: if dist[v] == -1: dist[v] = dist[u] + 1 queue.append(v) paths = [[] for _ in range(dist[end] + 1)] paths[0] = [start] for d in range(dist[end]): next_nodes = set() for u in paths[d]: for v, c in graph[u]: if dist[v] == dist[u] + 1: next_nodes.add((v, c)) next_nodes = sorted(next_nodes, key=lambda x: x[1]) paths[d + 1] = [v for v, c in next_nodes] result = [] for d in range(1, dist[end] + 1): result.append(paths[d][0]) return result n, m = map(int, input().split()) edges = [tuple(map(int, input().split())) for _ in range(m)] start, end = 1, n path = ideal_path(n, m, edges, start, end) print(" ".join(map(str, path))) 2.2.3 POJ2488 - A Knight’s Journey
题目解析
题目要求找到一个马在国际象棋棋盘上的 Hamiltonian path。即从一个起始点出发，访问所有的点且每个点只访问一次。可以使用回溯法（Backtracking）来解决这个问题。
代码示例
python
def is_valid(x, y, board): return 0 <= x < len(board) and 0 <= y < len(board[0]) and board[x][y] == -1 def knights_tour(n, m): board = [[-1 for _ in range(m)] for _ in range(n)] moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)] def backtrack(x, y, move_count): if move_count == n * m: return True for dx, dy in moves: nx, ny = x + dx, y + dy if is_valid(nx, ny, board): board[nx][ny] = move_count if backtrack(nx, ny, move_count + 1): return True board[nx][ny] = -1 return False board[0][0] = 0 if backtrack(0, 0, 1): return board else: return None n = 5 m = 5 result = knights_tour(n, m) if result: for row in result: print(" ".join(map(str, row))) else: print("No solution found.") 2.2.4 POJ3278 - Catch That Cow
题目解析
题目要求找到牛的最短路径，问题可以转化为一个最短路径问题，使用 BFS 来解决。
代码示例
python
from collections import deque def min_steps_to_catch_cow(start, target): if start >= target: return start - target max_pos = 2 * target visited = [False] * (max_pos + 1) queue = deque([(start, 0)]) while queue: position, steps = queue.popleft() if position == target: return steps for next_pos in (position - 1, position + 1, position * 2): if 0 <= next_pos <= max_pos and not visited[next_pos]: visited[next_pos] = True queue.append((next_pos, steps + 1)) start = int(input()) target = int(input()) print(min_steps_to_catch_cow(start, target)) 2.2.5 总结
这四道题目分别涉及图论中的连通分量计数、最短路径搜索、回溯法以及 BFS 搜索，都是常见的算法题。希望这些解析和代码示例能帮助你理解和解决这类问题。
3.图的连通性
3.1 桥、割点、连通分量、缩点
3.1.1 桥（Bridge）
概念
桥是图中的一条边，如果移除这条边会增加图的连通分量数目。也就是说，桥是将图分成两个连通部分的关键边。
代码示例
python
def find_bridges(graph): def dfs(u, parent, visited, discovery, low, time, bridges): visited[u] = True discovery[u] = low[u] = time[0] time[0] += 1 for v in graph[u]: if not visited[v]: dfs(v, u, visited, discovery, low, time, bridges) low[u] = min(low[u], low[v]) if low[v] > discovery[u]: bridges.append((u, v)) elif v != parent: low[u] = min(low[u], discovery[v]) n = len(graph) visited = [False] * n discovery = [float('inf')] * n low = [float('inf')] * n time = [0] bridges = [] for i in range(n): if not visited[i]: dfs(i, -1, visited, discovery, low, time, bridges) return bridges # 示例图 graph = { 0: [1, 2], 1: [0, 2], 2: [0, 1, 3, 4], 3: [2, 4], 4: [2, 3] } print(find_bridges(graph)) 3.1.2 割点（Cut Vertex / Articulation Point）
概念
割点是图中的一个顶点，如果移除这个顶点（以及相关的边）会增加图的连通分量数目。也就是说，割点是保持图连通的关键顶点。
代码示例
python
def find_articulation_points(graph): def dfs(u, parent, visited, discovery, low, time, ap): children = 0 visited[u] = True discovery[u] = low[u] = time[0] time[0] += 1 for v in graph[u]: if not visited[v]: children += 1 dfs(v, u, visited, discovery, low, time, ap) low[u] = min(low[u], low[v]) if parent == -1 and children > 1: ap[u] = True if parent != -1 and low[v] >= discovery[u]: ap[u] = True elif v != parent: low[u] = min(low[u], discovery[v]) n = len(graph) visited = [False] * n discovery = [float('inf')] * n low = [float('inf')] * n ap = [False] * n time = [0] for i in range(n): if not visited[i]: dfs(i, -1, visited, discovery, low, time, ap) return [index for index, is_ap in enumerate(ap) if is_ap] # 示例图 graph = { 0: [1, 2], 1: [0, 2], 2: [0, 1, 3, 4], 3: [2, 4], 4: [2, 3] } print(find_articulation_points(graph)) 3.1.3连通分量（Connected Component）
概念
连通分量是图中所有顶点的极大连通子图。每个连通分量内的任意两个顶点之间都有路径相连，而不同连通分量之间没有路径相连。
代码示例
python
def find_connected_components(graph): def dfs(node, visited, component): visited[node] = True component.append(node) for neighbor in graph[node]: if not visited[neighbor]: dfs(neighbor, visited, component) visited = [False] * len(graph) components = [] for node in range(len(graph)): if not visited[node]: component = [] dfs(node, visited, component) components.append(component) return components # 示例图 graph = { 0: [1], 1: [0, 2], 2: [1], 3: [4], 4: [3] } print(find_connected_components(graph)) 3.1.4 缩点（Condensation / SCC）
概念
缩点是将图中的强连通分量（SCC）缩成一个单一的节点。强连通分量是指有向图中任意两个顶点之间都有路径相连的极大子图。缩点操作后，原图的强连通分量被缩成一个顶点，形成DAG（有向无环图）。
代码示例
使用Tarjan算法找到SCC并进行缩点。
python
def tarjan_scc(graph): def dfs(u, index, lowlink, stack, on_stack, sccs): index[u] = lowlink[u] = index[0] index[0] += 1 stack.append(u) on_stack[u] = True for v in graph[u]: if index[v] == -1: dfs(v, index, lowlink, stack, on_stack, sccs) lowlink[u] = min(lowlink[u], lowlink[v]) elif on_stack[v]: lowlink[u] = min(lowlink[u], index[v]) if lowlink[u] == index[u]: scc = [] while True: v = stack.pop() on_stack[v] = False scc.append(v) if v == u: break sccs.append(scc) n = len(graph) index = [-1] * n lowlink = [0] * n on_stack = [False] * n stack = [] sccs = [] index[0] = 0 for i in range(n): if index[i] == -1: dfs(i, index, lowlink, stack, on_stack, sccs) return sccs # 示例图 graph = { 0: [1], 1: [2, 4, 5], 2: [3, 6], 3: [2, 7], 4: [0, 5], 5: [6], 6: [5], 7: [3, 6] } sccs = tarjan_scc(graph) print(sccs) # 缩点后的DAG def condensation_graph(sccs, graph): scc_map = {} for i, scc in enumerate(sccs): for node in scc: scc_map[node] = i dag = [[] for _ in range(len(sccs))] for u in range(len(graph)): for v in graph[u]: if scc_map[u] != scc_map[v]: dag[scc_map[u]].append(scc_map[v]) return dag dag = condensation_graph(sccs, graph) print(dag) 3.1.5 总结
- 桥：移除后增加连通分量的边。
- 割点：移除后增加连通分量的顶点。
- 连通分量：图中所有顶点的极大连通子图。
- 缩点：将强连通分量缩成一个单一节点，形成DAG。
这些概念和操作在图论中非常重要，理解和掌握它们对于解决图论问题至关重要。
3.2 tarjan算法
Tarjan算法是一种用于在有向图中寻找强连通分量（Strongly Connected Components, SCC）的线性时间算法。SCC是图中一个极大子图，其中任意两个顶点之间都有路径相连。Tarjan算法基于深度优先搜索（DFS），并利用DFS的访问顺序来确定SCC。
3.2.1 Tarjan算法的步骤
- 初始化：对于每个节点，初始化它们的索引号和低值，并使用一个栈来维护当前的访问路径。
- DFS遍历：在DFS遍历过程中，记录每个节点的索引号和低值，低值表示从该节点能到达的最早节点的索引号。
- 更新低值：在DFS过程中，如果当前节点能够通过后续节点回到前面的节点（存在后向边），则更新当前节点的低值。
- 识别SCC：当一个节点的低值等于它的索引号时，意味着找到了一个SCC，把栈中的节点弹出直到当前节点，并标记这些节点为一个SCC。
3.2.2 代码示例
以下是Tarjan算法的Python实现代码：
def tarjan_scc(graph): def dfs(node, index, lowlink, stack, on_stack, sccs): index[node] = lowlink[node] = index[0] index[0] += 1 stack.append(node) on_stack[node] = True for neighbor in graph[node]: if index[neighbor] == -1: dfs(neighbor, index, lowlink, stack, on_stack, sccs) lowlink[node] = min(lowlink[node], lowlink[neighbor]) elif on_stack[neighbor]: lowlink[node] = min(lowlink[node], index[neighbor]) if lowlink[node] == index[node]: scc = [] while True: v = stack.pop() on_stack[v] = False scc.append(v) if v == node: break sccs.append(scc) n = len(graph) index = [-1] * n lowlink = [0] * n on_stack = [False] * n stack = [] sccs = [] index[0] = 0 for i in range(n): if index[i] == -1: dfs(i, index, lowlink, stack, on_stack, sccs) return sccs # 示例图 graph = { 0: [1], 1: [2, 4, 5], 2: [3, 6], 3: [2, 7], 4: [0, 5], 5: [6], 6: [5], 7: [3, 6] } sccs = tarjan_scc(graph) print(sccs) 3.2.3 解释
- 初始化：在
tarjan_scc函数中，初始化了index和lowlink数组，on_stack布尔数组，以及stack和sccs列表。 - DFS遍历：通过递归的
dfs函数进行深度优先搜索。index记录节点的访问次序，lowlink记录节点能通过后续节点回溯到的最早访问节点的索引。 - 更新低值：在
dfs函数中，通过邻接节点的index和lowlink更新当前节点的lowlink。 - 识别SCC：如果当前节点的
lowlink等于其index，则找到一个 SCC，将栈中节点弹出并加入到当前 SCC 中，直到弹出当前节点。
3.2.4 总结
Tarjan算法高效地识别了图中的强连通分量，并且其时间复杂度为O(V + E)，其中V是节点数，E是边数。这使得Tarjan算法在处理大规模图结构时非常有用。
3.3 POJ1144、POJ3352、POJ2553、POJ1236
3.3.1 POJ1144 - Network Connections
题目解析
题目要求找到图中的割点（Articulation Points）。割点是指移除该顶点会增加图的连通分量数目的顶点。可以使用 Tarjan 算法来解决。
代码示例
def find_articulation_points(graph): def dfs(u, parent, visited, discovery, low, time, ap): children = 0 visited[u] = True discovery[u] = low[u] = time[0] time[0] += 1 for v in graph[u]: if not visited[v]: children += 1 dfs(v, u, visited, discovery, low, time, ap) low[u] = min(low[u], low[v]) if parent == -1 and children > 1: ap[u] = True if parent != -1 and low[v] >= discovery[u]: ap[u] = True elif v != parent: low[u] = min(low[u], discovery[v]) n = len(graph) visited = [False] * n discovery = [float('inf')] * n low = [float('inf')] * n ap = [False] * n time = [0] for i in range(n): if not visited[i]: dfs(i, -1, visited, discovery, low, time, ap) return [index for index, is_ap in enumerate(ap) if is_ap] # 输入处理 while True: n = int(input()) if n == 0: break graph = [[] for _ in range(n)] while True: line = input().strip() if line == '0': break edges = list(map(int, line.split())) u = edges[0] - 1 for v in edges[1:]: v -= 1 graph[u].append(v) graph[v].append(u) ap = find_articulation_points(graph) print(len(ap)) 3.3.2 POJ3352 - Road Construction
题目解析
题目要求找到图中的强连通分量（SCC），并使用缩点后的有向无环图（DAG）来确定需要添加多少条边可以使图强连通。可以使用 Tarjan 算法来找到 SCC。
代码示例
def tarjan_scc(graph): def dfs(u, index, lowlink, stack, on_stack, sccs): index[u] = lowlink[u] = index[0] index[0] += 1 stack.append(u) on_stack[u] = True for v in graph[u]: if index[v] == -1: dfs(v, index, lowlink, stack, on_stack, sccs) lowlink[u] = min(lowlink[u], lowlink[v]) elif on_stack[v]: lowlink[u] = min(lowlink[u], index[v]) if lowlink[u] == index[u]: scc = [] while True: v = stack.pop() on_stack[v] = False scc.append(v) if v == u: break sccs.append(scc) n = len(graph) index = [-1] * n lowlink = [0] * n on_stack = [False] * n stack = [] sccs = [] index[0] = 0 for i in range(n): if index[i] == -1: dfs(i, index, lowlink, stack, on_stack, sccs) return sccs # 输入处理 n, m = map(int, input().split()) graph = [[] for _ in range(n)] for _ in range(m): u, v = map(int, input().split()) graph[u - 1].append(v - 1) sccs = tarjan_scc(graph) # 缩点后的DAG scc_map = {} for i, scc in enumerate(sccs): for node in scc: scc_map[node] = i dag = [[] for _ in range(len(sccs))] indegree = [0] * len(sccs) outdegree = [0] * len(sccs) for u in range(n): for v in graph[u]: if scc_map[u] != scc_map[v]: dag[scc_map[u]].append(scc_map[v]) outdegree[scc_map[u]] += 1 indegree[scc_map[v]] += 1 in_zero = sum(1 for deg in indegree if deg == 0) out_zero = sum(1 for deg in outdegree if deg == 0) print(max(in_zero, out_zero)) 3.3.3 POJ2553 - Most Popular Element
题目解析
题目要求找到数组中出现次数最多的元素。可以使用哈希表来记录每个元素的出现次数，然后找到出现次数最多的元素。
代码示例
from collections import defaultdict while True: n = int(input()) if n == 0: break nums = list(map(int, input().split())) count = defaultdict(int) for num in nums: count[num] += 1 max_count = 0 most_popular = None for num in count: if count[num] > max_count: max_count = count[num] most_popular = num print(most_popular) 3.3.4 POJ1236 - Network of Schools
题目解析
题目要求找到图中的强连通分量（SCC），并确定在每个强连通分量中至少需要多少条边来使得图强连通。可以使用 Tarjan 算法来找到 SCC，并计算需要添加的边数。
代码示例
def tarjan_scc(graph): def dfs(u, index, lowlink, stack, on_stack, sccs): index[u] = lowlink[u] = index[0] index[0] += 1 stack.append(u) on_stack[u] = True for v in graph[u]: if index[v] == -1: dfs(v, index, lowlink, stack, on_stack, sccs) lowlink[u] = min(lowlink[u], lowlink[v]) elif on_stack[v]: lowlink[u] = min(lowlink[u], index[v]) if lowlink[u] == index[u]: scc = [] while True: v = stack.pop() on_stack[v] = False scc.append(v) if v == u: break sccs.append(scc) n = len(graph) index = [-1] * n lowlink = [0] * n on_stack = [False] * n stack = [] sccs = [] index[0] = 0 for i in range(n): if index[i] == -1: dfs(i, index, lowlink, stack, on_stack, sccs) return sccs # 输入处理 n = int(input()) graph = [[] for _ in range(n)] for i in range(n): connections = list(map(int, input().split())) for v in connections[:-1]: graph[i].append(v - 1) sccs = tarjan_scc(graph) # 缩点后的DAG scc_map = {} for i, scc in enumerate(sccs): for node in scc: scc_map[node] = i dag = [[] for _ in range(len(sccs))] indegree = [0] * len(sccs) outdegree = [0] * len(sccs) for u in range(n): for v in graph[u]: if scc_map[u] != scc_map[v]: dag[scc_map[u]].append(scc_map[v]) outdegree[scc_map[u]] += 1 indegree[scc_map[v]] += 1 in_zero = sum(1 for deg in indegree if deg == 0) out_zero = sum(1 for deg in outdegree if deg == 0) print(max(in_zero, out_zero)) 