信息奥赛｜图论基础与搜索

图论基础 简介 🚀

图论是信息奥赛中的重要内容。

图论中有不少 术语 需要掌握。

https://blog.csdn.net/raelum/article/details/129108365

图 是一个由点集 V = { v 1, v 2, · · · , v n} 和边集 E = { e 1, e 2, · · · , e m} 构成的结构.

一张图是连通图 ⇔ ∀v i, v j, i = ̸ j,∃ 一个首尾相连的边集 { e k1, e k2, · · · , e kt} , s.t. e k 1 = vi ,e k t = vj .

没有重边和自环的图称为简单图

有向图 & 无向图 若一张图的边集中的元素为有序对, 则这张图称为有向图; 反之则称为无 向图.

度 (degree) 与一个点相连的边的条数称为这个点的度. 特别地, 在有向图中, 指向一个点的 边的条数称为这个点的入度, 指向反向的边的条数称为这个点的出度, 出度加入度等于度. 可以证明在一张图中, 所有点的度数之和为偶数.

---

图（Graph）详解 ☘️

图的建立

图的建立方式一般有以下几种

• 邻接表（Vector）
• 邻接表（链式前向星）
• 邻接矩阵

无权图 - vector 存储

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;  // 最大顶点数量
vector<int> g[N];  // vector存储无权图

// 添加一条无权有向边：u -> v
void add_edge(int u, int v) {
    g[u].push_back(v); // 假设g[1]={2, 3}，表示存在边：1->2、1->3
}

int main() {
		// 读取边的数量
    int n, x, y;
    cin >> n;
  
    // 根据边来建图
    for (int i = 1; i <= n; i++) {
        // 添加一条 x->y 的有向边
        cin >> x >> y;
        add_edge(x, y);
    }

    return 0;
}

带权图 - vector 存储

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;  // 最大顶点数量
typedef pair<int, int> PII;  // pair.first存放该边指向的结点号，pair.second存放该边的权重w
vector<PII> g[N]; // vector存储带权图

// 添加一条带权有向边：u -> v
void add_edge(int u, int v, int w) {
    g[u].push_back({v, w});
}

int main() {
    // 读取边的数量
    int n, x, y, w;
    cin >> n;
    // 建图
    for (int i = 1; i <= n; i++) {
        cin >> x >> y >> w;
        // 添加一条 x->y 的带权有向边
        add_edge(x, y, w);
    }

    return 0;
}

图的遍历

BFS

DFS

---

vector OI 案例 🧑🏻‍💻

OI 案例1

【题目描述】

实现一个线性表: 参照 sq_delete 函数，对一个 $n$ 不超过 $1024$ 的线性表进行删除操作。

【输入】

第一行有一个整数 $n$，表示线性表的大小，第二行有 $n$ 个整数，分别是 list1, list2 … listn 。
第三行有一个整数 $q$，表示 $q$ 次删除操作，接下来 $q$ 行，每行有一个整数 $k$，表示删除线性表中第 $k$ 个元素。
(输入有多组测试数据，以 EOF 结束）

【输出】

对于每次删除操作输出一行，如果 $k$ 不合法，输出 $-1$, 否则输出删除的元素。

【输入样例】

5 
3 2 1 5 4 
3 
5 
5 
2

【输出样例】

4 
-1 
2

---

【题目分析】

本题使用 STL 容器，可以很大程度上简化代码。

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;
int n, q, tmp, id;
vector<int> v;
vector<int>::iterator it;

int main() {
    while (cin >> n) {
        v.clear();    //题目有多组样例，必须添加本行代码清空上一个v，否则会出错
        for (int i = 0; i < n; ++i) {
            cin >> tmp;
            v.push_back(tmp);
        }

        cin >> q;
        while (q--) {
            cin >> id;
            if (id < 1 || id > v.size()) {
                cout << -1 << endl;
            } else {
                it = v.begin();
                cout << *(it + id - 1)<<endl;   //vector 支持随机访问
                v.erase(it + id - 1);
            }
        }
    }
    return 0;
}