简介

图可以表示许多事物，从图像到无线信号皆可；最简单的类比之一是地图。设想一张 地图，其中有若干城市，并由双向道路连接。与图有关的问题包括：

1. 城市 $A$ 与城市 $B$ 是否连通？把一个区域定义为一组城市，其中每座城市都能 到达组内其他任意城市，却不能到达组外城市。这张地图中有多少个区域？每座城市 分别属于哪个区域？（USACO 银组）

2. 从城市 $A$ 到城市 $B$ 至少需要走多远？（USACO 金组）

对于 USACO 铜组，只需学习图的基本表示方法（通常是邻接表）。

构建邻接表

图通常以下列格式输入：

• 第一行包含节点数 $N$ 和边数 $M$。
• 接下来 $M$ 行，每行包含一对整数，表示图中的一条边。

例如，上述 CSAcademy 资料中的无向图 可以表示为以下输入：

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

也可以在 CSAcademy 图编辑器中可视化：

下面的代码用邻接表表示该图。得到这种表示后，就可以轻松输出某个节点的邻居数量， 或遍历一个节点的所有邻居。

Copy
N, M = map(int, input().split())
adj = [[] for _ in range(N)]

for i in range(M):
	u, v = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)

u = 1
# print number of vertices adjacent to u
print("deg(u) =", len(adj[u]))
# print all edges with u as an endpoint
for v in adj[u]:
	print("{" + str(u) + ", " + str(v) + "}")

输出：

deg(u) = 3
{1, 3}
{1, 4}
{1, 5}

铜组图论题是什么样的？

下面所有题目都至少属于以下两类之一：

• 图的结构特殊（它是一棵树、一条路径或一个环）。
• 只需遍历每个顶点的邻接表即可解决问题。

此外，了解银组图论主题通常会有所帮助，但并非解决这些题目 的必要条件。

Livestock Lineup

预期解法以 $\mathcal O(N\cdot C!)$ 的时间暴力枚举奶牛的所有排列；但如果用图表示 约束，只需 $\mathcal{O}(C)$ 时间即可解决。

使用图的解法

注意，由于输入保证有效，最终总能得到若干条可以任意排列的奶牛“链”。对题目给出的 样例，可以得到如下链式表示：

实现时，不属于任何链的奶牛可以各自视为一条长度为 $1$ 的链。

有了这种表示后，可以按字典序（字母顺序）遍历奶牛。当访问到可能作为链起点的奶牛 （至多有一个必须相邻的邻居）时，就沿着邻居反复前进，把访问到的奶牛加入排列， 直到抵达链的末端。

实现

时间复杂度： $\mathcal{O}(C)$

Copy
COWS = sorted(
	["Bessie", "Buttercup", "Belinda", "Beatrice", "Bella", "Blue", "Betsy", "Sue"]
)

cow_inds = {c: i for i, c in enumerate(COWS)}

neighbors = [[] for _ in range(len(COWS))]
with open("lineup.in") as read:
	for _ in range(int(read.readline())):
		words = read.readline().strip().split()

检查你的理解

题目