塔子哥の视频带读讲解

算法常识-树&图的读入和存储 (opens new window)

前言

只刷过LeetCode的同学在笔试阶段可能对ACM模式感到困惑。特别是对于树,图的读入以及存储。因为在核心代码模式中树的读入和存储都已经处理好了，而ACM模式中是直接让你读入规定格式的数据，然后自己存储。所以塔子哥这里写一篇文章来介绍一下树图的读入和存储。

什么是ACM模式？

​ 需要自己构造输入数据格式,评测平台不会给你任何代码,最后也需要我们自行输出。例如牛客,赛码。

什么是核心代码模式？

​ 功能函数已经给你封装好了，无需处理输入输出。直接返回结果即可。例如LeetCode

图的读入与存储

通常来说，图的读入形式有两种

1.给出所有边

给定边的个数和点的个数,通常记作$n,m$ , 接着给出$m$ 行，每行两个整数$u\ v$ 代表着第$i$条边所连接的两个点。此外，如果这张图带权，则每行就是三个整数，第三个整数是权值。例如题目:

P1224 携程-2023.04.15-春招-第三题-魔法之树 (opens new window)

以这道题为例:

1.读入一般使用语言自带的输入输出库即可。

2.存储通常使用可变长二维数组 ：开辟一个长度为$n$的数组，其中每个元素都是一个可变长数组(C++中就是vector ， Java中就是List , Python中就是list) 。具体见下方代码

• C++
• Java
• Python
• Go
• JavaScript

// 万能头,包含一切可能涉及到的库。各大平台都提供本头文件!
#include<bits/stdc++.h>
// 图的存储:开一个全局的定长数组，其中每个元素都是一个不定长数组vector<int>
// 开1001 是因为节点下标范围为[1,1000] , 所以需要多开一个
// 你所见到的开1005,1006也是这个原因。至少多开辟一位即可
vector<int> e[1001];

// ...

// 图的读入
int n;
cin >> n;
// 由于是树,所以只需要读n - 1 条边
for (int i = 1 ; i < n ; i++){
    int x , y;
    cin >> x >> y;
    e[x].push_back(y);
    // 由于你无法确认x,y之间谁是父亲节点，所以需要存双向边,
    // 在dfs的过程中防止返祖即可(返祖会引发死递归!)。
    e[y].push_back(x);
    // PS:在有一些题目里，他会明确规定谁是父亲,这种情况下就不用存双向边，
    // 且在dfs的过程中也不用担心返祖的问题.
}

// 图的存储:开一个全局的定长数组，其中每个元素都是一个不定长数组List<Integer>
// 开1001 是因为节点下标范围为[1,1000] , 所以需要多开一个
// 你所见到的开1005,1006也是这个原因。至少多开辟一位即可
List<Integer>[] e = new List[1001];

// ...

// 图的读入

// 在读入之前，记得需要初始化每一个List
for (int i = 1 ; i <= n ; i++){
    e[i] = new ArrayList<>();
}
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 1 ; i < n ; i++){
	int x = sc.nextInt();
	int y = sc.nextInt();
    e[x].add(y);
    // 由于你无法确认x,y之间谁是父亲节点，所以需要存双向边,
    // 在dfs的过程中防止返祖即可)(返祖会引发死递归!)。
    e[y].add(x);
    // PS:在有一些题目里，他会明确规定谁是父亲,这种情况下就不用存双向边，
    // 且在dfs的过程中也不用担心返祖的问题.
}

# 由于py自身栈深有限(1000) , 所以涉及到这种递归的题目需要手动开栈！
# 开栈的大小根据你的递归深度即可,一般开个2e6是稳的。
import sys
sys.setrecursionlimit(200000)

#... 

# 图的存储:开一个全局的定长list，其中每个元素都是一个list
# 开1001 是因为节点下标范围为[1,1000] , 所以需要多开一个
# 你所见到的开1005,1006也是这个原因。至少多开辟一位即可
e = [[] for i in range(1001)]

#...

# 图的读入
n = int(input())
for i in range(n):
    x , y = map(int,input().split())
    e[x].append(y)    
    # 由于你无法确认x,y之间谁是父亲节点，所以需要存双向边,
    # 在dfs的过程中防止返祖即可(返祖会引发死递归!)。
    e[y].append(x)
    # PS:在有一些题目里，他会明确规定谁是父亲,这种情况下就不用存双向边，
    # 且在dfs的过程中也不用担心返祖的问题.

// 图的存储:开一个定长数组，其中每个元素都是一个不定长数组[]
// 开1001 是因为节点下标范围为[1,1000] , 所以需要多开一个
// 你所见到的开1005,1006也是这个原因。至少多开辟一位即可
g = make([][]int, 1000+1)

// 初始化每一个数组
for i := 1; i <= n; i++ {
    g[i] = []int{}
}

// 图的读入
for i := 1; i < n; i++ {
    scanner.Scan()
    fields = strings.Fields(scanner.Text())
    a, _ := strconv.Atoi(fields[0])
    b, _ := strconv.Atoi(fields[1])
    g[a] = append(g[a], b)
    // 由于你无法确认x,y之间谁是父亲节点，所以需要存双向边,
    // 在dfs的过程中防止返祖即可)(返祖会引发死递归!)。
    g[b] = append(g[b], a)
    // PS:在有一些题目里，他会明确规定谁是父亲,这种情况下就不用存双向边，
    // 且在dfs的过程中也不用担心返祖的问题.
}

// Node.js 模板
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
});
process.stdin.on('end', () => {
    // write your code here
    let lines = input.trim().split('\n');
    let [n, l, r] = lines[0].split(' ').map(Number);
    let s = ['0'].concat(lines[1].split(''));
    // 图的存储:开一个大小为n + 1的定长数组，其中每个元素都是一个不定长数组[]
    // 开n + 1是因为节点下标范围为[1,n] , 所以需要多开一个
    // 你所见到的开n + 5 , n + 6也是这个原因。至少多开辟一位即可
    let g = new Array(n + 1);
    // 初始化数组每个元素为[]
    for (var i = 1 ; i <= n ; i++)
        g[i] = [];
    
    for(let i = 2; i < n + 1; i++){
        let [a, b] = lines[i].split(' ').map(Number);
        // 由于你无法确认x,y之间谁是父亲节点，所以需要存双向边,
        // 在dfs的过程中防止返祖即可)(返祖会引发死递归!)。
        g[a].push(b);
        g[b].push(a);
        // PS:在有一些题目里，他会明确规定谁是父亲,这种情况下就不用存双向边，
        // 且在dfs的过程中也不用担心返祖的问题.
    }
    let ans = 0;
    for(let i = 1; i <= n; i++){
        dfs(i, i, 0, 0);
    }
    console.log(ans);
    function dfs(cur, u, fa, val){
        val = val * 2 + Number(s[u]);
        if(val > r) return;
        if(val >= l && u !== cur) ans++;
        for(let v of g[u]){
            // 由于存的双向边，所以记录fa来防止返祖边
            if(v === fa) continue;
            dfs(cur, v, u, val);
        }
    }
    
});

2.给出邻接矩阵

给定点的个数$n$ , 接下来$n$ 行，直接给出邻接矩阵 , $a[i][j] = 1$ 代表$i,j$ 之间有一条边，$a[i][j]=0$ 代表没有边。例如题目:

华为-2022年9月23日-秋招机考-第三题-最省出游方案 (opens new window)

这种题目通常见于图中点的个数有限的情况 $n \leq 5000$

这里就不放具体代码了，这种情况我们直接定义二维数组即可。

树的读入与存储

1.存储 : 众所周知，树是无向无环图。所以存树和存图没有本质区别。 遇到树的题可以直接用上述方法存储。

2.读入：同时也是由于树的无向无环的性质，树具有一种独特的读入方式,即给出父亲节点数组:

给出$n-1$ 个正整数 $p[i]$ （ $2\le i \le n$ ）表示第 $i$ 个节点的父亲。规定 $1$ 号节点是根节点。例如题目:

P1141 美团-2023.04.01-第五题-染色の树 (opens new window)

这样的读入，我们只需要仿造上述方法，循环一遍$i:0 \rightarrow n-1$，将$(p[i],i+2)$ 当作一条单向边往$e$数组里插入即可。