算法笔试-图论
Updated Time
Category
Tags
关于语言：一刷用 Golang，二刷用 Rust
题单
基础遍历 DFS
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 547. 省份数量 | 中等 | ||
| 1971. 寻找图中是否存在路径 | 简单 | ||
| 797. 所有可能的路径 | 中等 |
BFS 基础
拓扑排序
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 1557. 可以到达所有点的最少点数目 | 第 33 场双周赛 Q2 | 中等 | 1512 |
| 210. 课程表 II | 中等 |
最短路
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 743. 网络延迟时间 | 中等 | ||
| 3112. 访问消失节点的最少时间 | 第 128 场双周赛 Q3 | 中等 | 1757 |
| 2642. 设计可以求最短路径的图类 | 第102 场周赛 Q4 | 困难 | 1811 |
| 3319. 第 K 大的完美二叉子树的大小 | 第 419 场周赛 Q2 | 中等 | 1603 |
| 1462. 课程表 IV | 第 27 场双周赛 Q3 | 中等 | 1693 |
| 1334. 阈值距离内邻居最少的城市 | 第 173 场周赛 Q3 | 中等 | 1855 |
| 2976. 转换字符串的最小成本 I | 第 377 场周赛 Q3 | 中等 | 1882 |
最小生成树
生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 \(n - 1\) 条，将所有顶点连通。
定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。
最小生成树算法，带输入与输出：
package main
import (
"bufio"
. "fmt"
"os"
)
const (
N int = 510
inf int = 2e9
)
var (
in *bufio.Reader
out *bufio.Writer
)
var n, m int
func prim(dis [][]int, root int) (mstSum int) {
// minD[i].d 表示 当前 MST 到点 i 的最小距离
minD := make([]int, len(dis))
for i := range minD {
minD[i] = inf
}
minD[root] = 0
// 初始所有的点都不在 MST 中
inMST := make([]bool, len(dis))
for i := 0; i < len(dis); i++ {
v := -1
for w, in := range inMST {
if !in && (v < 0 || minD[w] < minD[v]) {
v = w
}
}
inMST[v] = true
if i > 0 && minD[v] == inf {
return inf
}
mstSum += minD[v]
for w, d := range dis[v] {
minD[w] = min(minD[w], d)
}
}
return
}
func main() {
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
defer out.Flush()
Fscan(in, &n, &m)
g := make([][]int, n)
for i := 0; i < n; i++ {
g[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
g[i][j] = inf
}
}
var u, v, w int
for i := 0; i < m; i++ {
Fscan(in, &u, &v, &w)
u, v = u-1, v-1
g[u][v] = min(g[u][v], w)
g[v][u] = min(g[v][u], w)
}
ans := prim(g, 0)
if ans == inf {
Fprintln(out, "impossible")
} else {
Fprintln(out, ans)
}
}
//go:build ignore
// +build ignore
package main
import (
"bufio"
. "fmt"
"os"
"slices"
)
const inf int = 2e9
var (
in *bufio.Reader
out *bufio.Writer
n, m int
)
func kruskal(n int, edges [][]int) int {
slices.SortFunc(edges, func(a, b []int) int {
return a[2] - b[2]
})
fa := make([]int, n)
for i := range fa {
fa[i] = i
}
var find func(int) int
find = func(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
sum, cnt := 0, 0
for _, e := range edges {
u, v, w := e[0], e[1], e[2]
fu, fv := find(u), find(v)
if fu != fv {
fa[fv] = fu
sum += w
cnt++
}
}
// 图不联通
if cnt < n-1 {
return inf
}
return sum
}
func main() {
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
defer out.Flush()
Fscan(in, &n, &m)
g := make([][]int, m)
var u, v, w int
for i := 0; i < m; i++ {
Fscan(in, &u, &v, &w)
u, v = u-1, v-1
g[i] = []int{u, v, w}
}
ans := kruskal(n, g)
if ans == inf {
Fprintln(out, "impossible")
} else {
Fprintf(out, "%d\n", ans)
}
}
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 1584. 连接所有点的最小费用 | 第 206 场周赛 Q3 | 中等 | 1858 |
连通分量
二分图
染色法判断是否是二分图：
func isBipartite(g [][]int) bool {
colors := make([]int, len(g))
var dfs func(int, int) bool
dfs = func(u int, c int) bool {
colors[u] = c
for _, v := range g[u] {
if colors[v] == c || colors[v] == 0 && !dfs(v, c ^ 1) {
return false
}
}
return true
}
for i, c := range colors {
if c != 0 {
continue
}
if !dfs(i, 2) {
return false
}
}
return true
}
匈牙利算法求最大匹配数：
func hungarian(g [][]int) (match []int, cnt int) {
match = make([]int, n1 + n2 + 1)
for i := range match {
match[i] = -1
}
var used []bool
var dfs func(int) bool
dfs = func(u int) bool {
for _, v := range g[u] {
if !used[v] {
used[v] = true
if match[v] == -1 || dfs(match[v]) {
match[v] = u
return true
}
}
}
return false
}
for i := 1; i <= n1; i++ {
used = make([]bool, n1 + n2 + 1)
if dfs(i) {
cnt++
}
}
return
}
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 1093D. Beautiful Graph | Educational Codeforces Round 56 (Rated for Div. 2) | 1700 |
网络流
题解
547. 省份数量
func findCircleNum(isConnected [][]int) (ans int) {
n := len(isConnected)
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if vis[i] {
return
}
vis[i] = true
for j, ok := range isConnected[i] {
if ok == 1 {
dfs(j)
}
}
}
for i := 0; i < n; i++ {
if !vis[i] {
dfs(i)
ans++
}
}
return
}
1971. 寻找图中是否存在路径
func validPath(n int, edges [][]int, source int, destination int) bool {
g := make([][]int, n)
for i := range g {
g[i] = make([]int, 0)
}
for _, edge := range edges {
u, v := edge[0], edge[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
vis := make([]bool, n)
var dfs func(int) bool
dfs = func(u int) bool {
if u == destination {
return true
}
vis[u] = true
for _, v := range g[u] {
if !vis[v] && dfs(v) {
return true
}
}
return false
}
return dfs(source)
}
797. 所有可能的路径
func allPathsSourceTarget(graph [][]int) (ans [][]int) {
path := []int{0}
var dfs func(int)
dfs = func(i int) {
if i == len(graph) - 1 {
ans = append(ans, append([]int{}, path...))
return
}
for _, v := range graph[i] {
path = append(path, v)
dfs(v)
path = path[:len(path) - 1]
}
}
dfs(0)
return
}
743. 网络延迟时间
仅此题目用朴素 dijkstra，堆优化 dijkstra，spfa 写，后续题目只选择最合适的。
func networkDelayTime(times [][]int, n int, k int) int {
const inf = math.MaxInt / 2 // 防止加法溢出
g := make([][]int, n + 1) // 邻接矩阵
for i := range g {
g[i] = make([]int, n + 1)
for j := range g[i] {
g[i][j] = inf
}
}
for _, t := range times {
u, v, w := t[0], t[1], t[2]
g[u][v] = min(g[u][v], w)
}
dist := make([]int, n + 1)
for i := range dist {
dist[i] = inf
}
dist[0] = 0
dist[k] = 0
st := make([]int, n + 1)
for i := 1; i < n; i++ {
t := -1
for j := 1; j <= n; j++ {
if st[j] == 0 && (t == -1 || dist[t] > dist[j]) {
t = j
}
}
st[t] = 1
for j := 1; j <= n; j++ {
dist[j] = min(dist[j], dist[t] + g[t][j])
}
}
ans := 0
for _, v := range dist {
ans = max(ans, v)
}
if ans == inf {
return -1
}
return ans
}
const INF = 0x3f3f3f3f
type edge struct {
to, w int
}
type hp []edge
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].w < h[j].w }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(edge)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
func networkDelayTime(times [][]int, n int, k int) int {
g := make([][]edge, n+1)
for i := range times {
e := times[i]
u, v, w := e[0], e[1], e[2]
g[u] = append(g[u], edge{v, w})
}
dist := make([]int, n+1)
for i := range dist {
dist[i] = INF
}
dist[k] = 0
h := hp{edge{k, 0}}
for len(h) > 0 {
cur := heap.Pop(&h).(edge)
v, d := cur.to, cur.w
if dist[v] < d {
continue
}
for _, e := range g[v] {
w := e.to
if newDis := d + e.w; newDis < dist[w] {
dist[w] = newDis
heap.Push(&h, edge{w, newDis})
}
}
}
ans := 0
for i := 1; i <= n; i++ {
if dist[i] == INF {
return -1
}
ans = max(ans, dist[i])
}
return ans
}
func networkDelayTime(times [][]int, n int, k int) int {
const inf = math.MaxInt / 2
g := make([][]edge, n + 1)
for _, t := range times {
u, v, w := t[0], t[1], t[2]
g[u] = append(g[u], edge{v, w})
}
dist := make([]int, n + 1)
for i := range dist {
dist[i] = inf
}
dist[k] = 0
pq := priorityqueue.NewWith(func (a, b interface{}) int {
return a.(edge).w - b.(edge).w
})
pq.Enqueue(edge{k, 0})
for pq.Size() > 0 {
cur, _ := pq.Dequeue()
v, d := cur.(edge).to, cur.(edge).w
if dist[v] < d {
continue
}
for _, e := range g[v] {
w := e.to
if newDis := d + e.w; newDis < dist[w] {
dist[w] = newDis
pq.Enqueue(edge{w, newDis})
}
}
}
ans := 0
for i := 1; i <= n; i++ {
if dist[i] == inf {
return -1
}
ans = max(ans, dist[i])
}
return ans
}
type edge struct {
to, w int
}
var (
he, dist [110]int
e, w, ne [6010]int
st [100]bool
idx = 0
)
const inf = math.MaxInt / 2
func add(a, b, c int) {
w[idx] = c
e[idx] = b
ne[idx] = he[a]
he[a] = idx
idx++
}
func networkDelayTime(times [][]int, n int, k int) int {
idx = 0
for i := range dist {
dist[i] = inf
}
for i := range he {
he[i] = -1
}
for _, t := range times {
u, v, w := t[0], t[1], t[2]
add(u, v, w)
}
q := []int{}
q = append(q, k)
dist[k] = 0
st[k] = true
for len(q) > 0 {
t := q[0]
q = q[1:]
st[t] = false
for i := he[t]; i != -1; i = ne[i] {
j := e[i]
if dist[j] > dist[t] + w[i] {
dist[j] = dist[t] + w[i]
if !st[j] {
st[j] = true
q = append(q, j)
}
}
}
}
ans := 0
for i := 1; i <= n; i++ {
if dist[i] == inf {
return -1
}
ans = max(ans, dist[i])
}
return ans
}
3112. 访问消失节点的最少时间
func minimumTime(n int, edges [][]int, disappear []int) []int {
g := make([][]edge, n)
for _, e := range edges {
u, v, w := e[0], e[1], e[2]
g[u] = append(g[u], edge{v, w})
g[v] = append(g[v], edge{u, w})
}
dist := make([]int, n)
for i := range dist {
dist[i] = -1
}
pq := priorityqueue.NewWith(func (a, b interface{}) int {
return a.(edge).w - b.(edge).w
})
dist[0] = 0
pq.Enqueue(edge{0, 0})
for pq.Size() > 0 {
cur, _ := pq.Dequeue()
v, d := cur.(edge).to, cur.(edge).w
if dist[v] < d {
continue
}
for _, e := range g[v] {
newDis := d + e.w
if newDis < disappear[e.to] && (dist[e.to] == -1 || newDis < dist[e.to]) {
dist[e.to] = newDis
pq.Enqueue(edge{e.to, newDis})
}
}
}
return dist
}
type edge struct {
to, w int
}
2642. 设计可以求最短路径的图类
type edge struct {
v, w int
}
type Graph struct {
n int
g [][]edge
}
func Constructor(n int, edges [][]int) Graph {
g := make([][]edge, n)
for _, e := range edges {
u, v, w := e[0], e[1], e[2]
g[u] = append(g[u], edge{v, w})
}
return Graph{
n: n,
g: g,
}
}
func (this *Graph) AddEdge(e []int) {
u, v, w := e[0], e[1], e[2]
this.g[u] = append(this.g[u], edge{v, w})
}
func (this *Graph) ShortestPath(node1 int, node2 int) int {
dist := make([]int, this.n)
for i := range dist {
dist[i] = -1
}
pq := priorityqueue.NewWith(func (a, b interface{}) int {
return a.(edge).w - b.(edge).w
})
dist[node1] = 0
pq.Enqueue(edge{node1, 0})
for pq.Size() > 0 {
cur, _ := pq.Dequeue()
v, w := cur.(edge).v, cur.(edge).w
if dist[v] < w {
continue
}
for _, e := range this.g[v] {
if newDis := w + e.w; (dist[e.v] == -1 || newDis < dist[e.v]) {
dist[e.v] = newDis
pq.Enqueue(edge{e.v, newDis})
}
}
}
return dist[node2]
}
3319. 第 K 大的完美二叉子树的大小
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthLargestPerfectSubtree(root *TreeNode, k int) int {
var dfs func(*TreeNode) int
ms := make([]int, 0)
dfs = func(c *TreeNode) int {
if c == nil {
return 0
}
l, r := dfs(c.Left), dfs(c.Right)
if l == -1 || r == -1 {
return -1
} else if l == r {
ms = append(ms, l + r + 1)
return l + r + 1
} else {
return -1
}
}
dfs(root)
slices.Sort(ms)
if len(ms) < k {
return -1
}
return ms[len(ms) - k]
}
1584. 连接所有点的最小费用
func minCostConnectPoints(points [][]int) int {
const inf int = 2e9
dis := func(a, b []int) int {
return abs(a[0] - b[0]) + abs(a[1] - b[1])
}
n := len(points)
dist := make([][]int, len(points))
for i := range dist {
dist[i] = make([]int, n)
for j := range dist[i] {
dist[i][j] = dis(points[i], points[j])
}
}
minD := make([]int, n)
for i := range minD {
minD[i] = inf
}
inMST := make([]bool, n)
minD[0] = 0
mstSum := 0
for {
v := -1
for w, in := range inMST {
if !in && (v < 0 || minD[w] < minD[v]) {
v = w
}
}
if v == -1 {
break
}
inMST[v] = true
mstSum += minD[v]
for w, d := range dist[v] {
minD[w] = min(minD[w], d)
}
}
return mstSum
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
1557. 可以到达所有点的最少点数目
func findSmallestSetOfVertices(n int, edges [][]int) (ans []int) {
in := make([]bool, n)
for _, e := range edges {
in[e[1]] = true
}
for i, b := range in {
if !b {
ans = append(ans, i)
}
}
return
}
210. 课程表 II
func findOrder(numCourses int, prerequisites [][]int) (ans []int) {
g := make([][]int, numCourses)
for i := range g {
g[i] = make([]int, 0)
}
din := make([]int, numCourses)
for _, p := range prerequisites {
u, v := p[1], p[0]
g[u] = append(g[u], v)
din[v]++
}
q := []int{}
for i := 0; i < numCourses; i++ {
if din[i] == 0 {
q = append(q, i)
}
}
for len(q) > 0 {
t := q[0]
q = q[1:]
ans = append(ans, t)
for _, v := range g[t] {
din[v]--
if din[v] == 0 {
q = append(q, v)
}
}
}
if len(ans) != numCourses {
return []int{}
}
return
}
1462. 课程表 IV
Floyd 求最短路
func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
g := make([][]bool, numCourses)
for i := range g {
g[i] = make([]bool, numCourses)
}
for _, p := range prerequisites {
u, v := p[0], p[1]
g[u][v] = true
}
for k := 0; k < numCourses; k++ {
for i := 0; i < numCourses; i++ {
for j := 0; j < numCourses; j++ {
if g[i][k] && g[k][j] {
g[i][j] = true
}
}
}
}
ans := make([]bool, len(queries))
for i, q := range queries {
ans[i] = g[q[0]][q[1]]
}
return ans
}
1334. 阈值距离内邻居最少的城市
func findTheCity(n int, edges [][]int, distanceThreshold int) (ans int) {
g := make([][]int, n)
const inf int = 2e9
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = inf
}
}
for _, edge := range edges {
u, v, w := edge[0], edge[1], edge[2]
g[u][v] = w
g[v][u] = w
}
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
g[i][j] = min(g[i][j], g[i][k] + g[k][j])
}
}
}
mn := n
for i := 0; i < n; i++ {
cnt := 0
for j := 0; j < n; j++ {
if i != j && g[i][j] <= distanceThreshold {
cnt++
}
}
if cnt <= mn {
mn = cnt
ans = i
}
}
return
}
2976. 转换字符串的最小成本 I
func minimumCost(source string, target string, original []byte, changed []byte, cost []int) (ans int64) {
g := make([][]int, 26)
for i := range g {
g[i] = make([]int, 26)
for j := range g[i] {
if i != j {
g[i][j] = 1e13
}
}
}
for i := range original {
u, v := original[i] - 'a', changed[i] - 'a'
g[u][v] = min(g[u][v], cost[i])
}
for k := 0; k < 26; k++ {
for i := 0; i < 26; i++ {
for j := 0; j < 26; j++ {
g[i][j] = min(g[i][j], g[i][k] + g[k][j])
}
}
}
for i := range source {
u, v := source[i] - 'a', target[i] - 'a'
ans += int64(g[u][v])
}
if ans >= 1e13 {
return -1
}
return
}
1093D. Beautiful Graph
给出一个无向图，每个节点可以填 \(1,2,3\) 三个数中的一个。询问有多少种填数方案，使两个相邻节点之和为奇数。
如果图中有奇数环，一定无解。所以可以对图进行染色。记第 \(i\) 个联通分量的黑点数量为 \(b_i\)，白点数量为 \(w_i\)。每一条连接的两个节点，一个是 \(2\)，另一个是 \(1\) 或 \(3\)。如果黑点全部填 \(2\)，否则白点全部填 \(2\)。 - 若黑点填 \(2\)，则剩下白点有 \(2^{w_i}\) 种填法。 - 若白点填 \(2\)，则剩下的黑点有 \(2^{b_i}\) 种填法。
//go:build ignore
// +build ignore
package main
import (
"bufio"
. "fmt"
"os"
)
var (
in *bufio.Reader
out *bufio.Writer
n, m int
g [][]int
pow2 [3e5 + 10]int64
)
const mod int64 = 998244353
func init() {
const mx int = 3e5
pow2 = [3e5 + 10]int64{1}
for i := 1; i <= mx; i++ {
pow2[i] = pow2[i-1] << 1 % mod
}
}
func solve() {
Fscan(in, &n, &m)
g = make([][]int, n)
var u, v int
for ; m > 0; m-- {
Fscan(in, &u, &v)
u, v = u-1, v-1
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
cnt := [3]int{}
colors := make([]int, n)
var dfs func(int, int) bool
dfs = func(u, c int) bool {
colors[u] = c
cnt[c]++
for _, v := range g[u] {
if colors[v] == c || colors[v] == 0 && !dfs(v, 3^c) {
return false
}
}
return true
}
ans := int64(1)
for i, c := range colors {
if c == 0 {
cnt = [3]int{}
if !dfs(i, 1) {
Fprintln(out, 0)
return
}
ans = ans * (pow2[cnt[1]] + pow2[cnt[2]]) % mod
}
}
Fprintln(out, ans)
}
func main() {
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
defer out.Flush()
var T int
for Fscan(in, &T); T > 0; T-- {
solve()
}
}