\(noip\ Templates\)
\(Part 1 \ Graph\)
- Toposort
- Dijkstra
- SPFA
- Floyd
- Kruskal
- Prim
- Tarjan
- LCA
\(Graph\)
0. 链式前向星存图
int h[N], e[N], ne[N], idx; // 对于每个点k开一个单链表，存储所有可以走到的点。h[k]存储单链表头结点
// 添加一条边a->b
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
1. Toposort
bool toposort() {
int hh = 0, tt = -1;
for (int i = 1; i <= n; i++) if (!d[i]) q[++tt] = i; // d[i] 存储点i的入度
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (--d[j] == 0) q[++tt] = j;
}
}
return tt == n - 1; // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
}
2. Dijkstra
int n, h[N], w[N], e[N], ne[N], idx, dist[N]; // 邻接表存储所有边, dist[N]存储所有点到1号点距离
bool st[N]; // 存储每个点的最短距离是否已确定
int dijkstra() { // 求1号点到n号点的最短距离，如果不存在，则返回-1
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离，second存储节点编号
while (heap.size()) {
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) dist[j] = distance + w[i], heap.push({dist[j], j});
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
3. SPFA
int n, h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
int spfa() { // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
memset(dist, 0x3f, sizeof dist);
queue<int> q;
q.push(1), st[1] = true, dist[1] = 0;
while (q.size()) {
auto t = q.front();
q.pop(), st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) q.push(j), st[j] = true; // 如果队列中已存在j，则不需要将j重复插入
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int n, h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
bool spfa() { // 如果存在负环，则返回true，否则返回false。不需要初始化dist数组, 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
queue<int> q;
for (int i = 1; i <= n; i++) q.push(i), st[i] = true;
while (q.size()) {
auto t = q.front();
q.pop(), st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i], cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果从1号点到x最短路中包含至少n个点（不包括自己），则存在环
if (!st[j]) q.push(j), st[j] = true;
}
}
}
return false;
}
4. Floyd
void init() {
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = (i == j) ? 0 : INF;
}
void floyd() { // 算法结束后，d[a][b]表示a到b的最短距离
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
5. Kruskal
int n, m, p[N]; // n是点数，m是边数, p[N]是并查集的父节点数组
struct Edge { // 存储边
int a, b, w;
bool operator< (const Edge &W)const {return w < W.w;}
}edges[M];
int find(int x) { // 并查集核心操作
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal() {
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ ) {
int a = find(edges[i].a), b = find(edges[i].b), w = edges[i].w;
if (a != b) p[a] = b, res += w, cnt++; // 如果两个连通块不连通，则将这两个连通块合并
}
if (cnt < n - 1) return INF;
return res;
}
6. Prim
int n, g[N][N]; // n表示点数, g[N][N]邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
int prim() { // 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
7. Tarjan
int n, m, val[N], dfn[N], low[N], num, col[N], cnt, st[N], top;
// col记录每个点属于哪个联通分量, num记录遍历时间, cnt记录缩点完后有多少个点
queue<int> q;
int new_val[N], du[N], f[N], ans;
vector<int> g[N], new_g[N];
void tarjan(int x) {
dfn[x] = low[x] = ++num; st[++top] = x; //更新这个点
for (int i = 0; i < g[x].size(); i++) {
int t = g[x][i];
if (!dfn[t]) tarjan(t), low[x] = min(low[x], low[t]); // 往下更新（要确保下个点没被更新）
else if (!col[t])low[x] = min(low[x], dfn[t]); // 被更新了，但没被划分到强连通分量里
}
if (dfn[x] == low[x])
for (cnt++; st[top + 1] != x; top--)
col[st[top]] = cnt, new_val[cnt] += val[st[top]]; // 找到这个连通分量的代表，划分
// 为什么要有low? 因为我们最后要划分强连通分量（上面的操作），但不知道什么时候划分，所以添一个low。
// 当dfn==low时就统计，这样不重不漏。
}
int main() {
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); // 这个点仍不在任一个强连通分量里
// 目的：把每个点都放进一个强连通分量里，这样缩点完后就不存在环，就可以拓扑排序了
// 所以流程就是：
// 1.缩点,使整个图无环，方便后面拓扑排序 复杂度：O(n+m)
// 2.拓扑排序找最大路径 复杂度：O(m)
for (int i = 1; i <= n; i++)
for (int j = 0; j < g[i].size(); j++) {
int t = g[i][j];
if (col[i] != col[t]) new_g[col[i]].push_back(col[t]), du[col[t]]++; // 记录新图的边
}
}
8. LCA
int n, m, h[N], e[M], ne[M], idx, depth[N], fa[N][16], q[N];
void bfs(int root) {
memset(depth, 0x3f, sizeof depth);
int hh = 0, tt = 0;
depth[0] = 0, depth[root] = 1, q[0] = root;
while (hh <= tt) {
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (depth[j] > depth[t] + 1) {
depth[j] = depth[t] + 1, q[ ++ tt] = j, fa[j][0] = t;
for (int k = 1; k <= 15; k++) fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k--) if (depth[fa[a][k]] >= depth[b]) a = fa[a][k];
if (a == b) return a;
for (int k = 15; k >= 0; k--) if (fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
return fa[a][0];
}