1
#include <iostream>
2
#include <queue>
3
#include <vector>
4
using namespace std;
5

6
void BFS(vector<vector<int>>& graph, int start) {
7
    vector<bool> visited(graph.size(), false);
8
    queue<int> q;
9
    q.push(start);
10
    visited[start] = true;
11

12
    while (!q.empty()) {
13
        int node = q.front();
14
        q.pop();
15
        cout << node << " "; // 处理节点
16
        for (int neighbor : graph[node]) {
17
            if (!visited[neighbor]) {
18
                visited[neighbor] = true;
19
                q.push(neighbor);
20
            }
21
        }
22
    }
23
}
24

25
// 示例：邻接表图遍历
26
int main() {
27
    vector<vector<int>> graph = {{1,2}, {0,3}, {0,3,4}, {1,2,4}, {2,3}};
28
    cout << "BFS顺序：";
29
    BFS(graph, 0); // 输出：0 1 2 3 4
30
    return 0;
31
}

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <unordered_map>
5
using namespace std;
6

7
vector<string> shortest_path(unordered_map<string, vector<string>>& graph,
8
                           string start, string end) {
9
    queue<string> q;
10
    unordered_map<string, bool> visited;
11
    unordered_map<string, string> parent;  // 记录路径父节点
12

13
    q.push(start);
14
    visited[start] = true;
15
    parent[start] = "";
16

17
    while (!q.empty()) {
18
        string cur = q.front();
19
        q.pop();
20
        if (cur == end) {
21
            // 反向回溯路径
22
            vector<string> path;
23
            for (string at = end; at != ""; at = parent[at])
24
                path.push_back(at);
25
            reverse(path.begin(), path.end());
26
            return path;
27
        }
28
        for (string neighbor : graph[cur]) {
29
            if (!visited[neighbor]) {
30
                visited[neighbor] = true;
31
                parent[neighbor] = cur;  // 记录父节点
32
                q.push(neighbor);
33
            }
34
        }
35
    }
36
    return {}; // 无路径
37
}

1
#include <algorithm>
2
#include <vector>
3
using namespace std;
4

5
// 活动选择问题（最早结束优先）
6
struct Activity { int start, end; };
7
bool compare(Activity a, Activity b) { return a.end < b.end; }
8

9
int maxActivities(vector<Activity>& acts) {
10
    sort(acts.begin(), acts.end(), compare);
11
    int count = 1, lastEnd = acts[0].end;
12
    for (int i = 1; i < acts.size(); i++) {
13
        if (acts[i].start >= lastEnd) {
14
            count++;
15
            lastEnd = acts[i].end;
16
        }
17
    }
18
    return count;
19
}

1
vector<int> prefix(n + 1, 0);
2
for (int i = 1; i <= n; i++)
3
    prefix[i] = prefix[i-1] + arr[i-1];
4

5
// 查询 [L, R] 和：sum = prefix[R] - prefix[L-1];

1
// 预处理
2
vector<vector<int>> sum(n+1, vector<int>(m+1, 0));
3
for (int i = 1; i <= n; i++)
4
    for (int j = 1; j <= m; j++)
5
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
6

7
// 查询 (x1,y1) 到 (x2,y2) 和：
8
int area = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];

1
vector<int> diff(n + 2, 0); // 多开空间防越界
2

3
void add(int l, int r, int k) {
4
    diff[l] += k;
5
    diff[r+1] -= k;
6
}
7

8
// 还原数组
9
for (int i = 1; i <= n; i++)
10
    arr[i] = arr[i-1] + diff[i];

1
// 拼接字符串使字典序最小
2
sort(strs.begin(), strs.end(), [](string a, string b) {
3
    return a + b < b + a;
4
});
5
string ans;
6
for (string s : strs) ans += s;