1. 建图
分为邻接表 和 邻接矩阵两种 邻接表用的比较多
Copy int n, m; // node 和 edge
int h[N], e[N], ne[N], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
} 2. 拓扑排序
拓扑排序就是统计每个点的入度，入度为0的一定在前面, 遍历每个入度为0的点，把他的邻接点的入度减1， 重复这个操作就得到拓扑排序的序列了；
此外，只有有向无环图才有拓扑排序 所以也是判断有没有环的一种方式；
Copy int n, m;
int h[N], ne[N], idx;
int q[N], d[N]; // 模拟栈 入度din
int add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++, d[b]++; // 额外统计b的入度
}
bool topsort()
{
int hh = 0, tt = -1;
for(int i = 1; i <= n; i++)
{
if(d[i] == 0) q[++tt] = i; // 入栈
}
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
d[j]--;
if(d[j] == 0) q[++tt] = j;
}
}
// 出栈顺序 也就是拓扑排序的顺序
return tt == n - 1;
} 3. 最短路问题
最短路问题要写的可就多了 也是趁这机会好好复习一下吧
最短路问题主要记的有以下几个方法：
堆优化dijkstra, Bellman-Ford, SPFA, Floyd; 其实还有双端队列BFS(0 - 1 边权的最短路问题), 等会也写上吧
1. 堆优化版dijkstra: 适用于正（其实是非负）边权
记住dijkstra是出栈（出队）时确定最小距离就好了
Copy typedef pair<int, int> PII; // 距离 + 编号
int n;
int h[N], w[N], e[N], ne[N], idx;
int dist[N]; // 存储每个点 和 1 的距离
bool st[N]; // 每个点的最短距离是否已经确定
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0；
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.emplace(0, 1);
while(heap.size())
{
PII t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
// 记住了 dijkstra是在出队确定
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.emplace(dist[j], j);
}
}
}
if(dist[n] = 0x3f3f3f3f) return -1;
else return dist[n];
}
memset(h, -1, sizeof h);
2. Bellman-Ford
现在看来， Bellman-Ford 算法最适合解决的问题是有边数限制的最短路问题 剩下比如有负权边的最短路问题，负环的判断等等都可以用SPFA 来解决
Copy int n, m;
int dist[N];
struct Edge
{
int a, b, w;
}edges[M];
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n; i++) // 在这里 这里的循环次数就是边数限制
for(int j = 0; j < m; j++)
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
if(dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
// 注意这里的判断
if(dist[n] > 0x3f3f3f3f / 2)
return -1;
return dist[n];
} 3. SPFA:(正负都可以）
spfa 的代码其实和堆优化dijkstra很像 因为都是用堆去优化那个找当前最小距离的过程;
这两个的判断条件不一样 要记清:
但是spfa是出队都没有办法保证是最短距离，只要更新就要入栈，st数组的意义在于如果栈中有这个元素就不必再次加入了（因为肯定是要重算）
1. SPFA 求最短路
Copy int n;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > w[i] + dist[t])
{
dist[j] = w[i] + dist[t];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
} 2. SPFA 判断是否存在负环
相较于求最短路 额外围护一个cnt数组，这个数组记录最短路径的节点数量 只要超过 n + 1 则证明必有负环存在
注意这里要把所有点都加入队列，dist清空or not 都无所谓 避免起点与负环不连通-> 找不到
找正环 : 把求最短路变成求最长路即可！
常用于0-1分数规划问题
除了这个之外还有个额外的trick，如果超时了的话 可以按照spfa出栈元素的次数判断是否存在负环 如果出栈元素的次数大于一个经验值（可以试一试 2*n 3*n）就可以当成有负环了
Copy int n;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], cnt[N];
bool st[N];
bool spfa()
{
memset(dist, 0, sizeof dist);
queue<int> q;
for(int i = 1; i <= n; i++)
{
q.push(1);
st[1] = true;
}
while(q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; 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;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
} 4. floyd: 多源汇最短路
基于动态规划 记住那三重循环的顺序 先遍历的是中间点k
Copy for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
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]);
} 同样的 可以将floyd退化为bool值 这样直接判断是否连通
5. 双端队列BFS: (只有0-1边权的最短路问题)
对于只有0 - 1 两种边权的最短路问题，可以用双端队列广搜来实现 不必维护一个heap;
Copy int bfs()
{
memset(st, false, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
deque<int> q;
q.push_back(1);
while(q.size())
{
int t = q.front();
q.pop_front();
if(st[t]) continue;
st[t] = true;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] < dist[t] + w[i]) // 这里w[1] 只会取0 1
{
dist[j] = dist[t] + w[i];
if(w[i]) q.push_back(j);
else q.push_front(j);
}
}
}
return dist[n];
} 4.最小生成树问题
最小生成树就记一个Kruskal算法就好；
Kruskal 算法
Kruskal算法基于的是并查集，整体思路很简单, 将所有边按权重从小到大排序，枚举所有边(a, b, w) 如果 a b尚未连通，就将这条边加入集合中 并统计权重就好了；
Copy struct Edge
{
int a, b, w;
bool operator<(const Edge& e) const
{
return this->w < e.w;
}
}edges[2 * N];
int p[N];
int find(int a)
{
if(p[a] != a) p[a] = find(p[a]);
return p[a];
}
// 并查集初始化
for(int i = 1; i <= n; i++)
p[i] = i;
// 读入edges
...
int res = 0, cnt = 0;
for(int i = 0; i < n; i++)
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
if(find(a) != find(b))
{
p[find(a)] = find(b);
res += w;
cnt++;
}
}
// 最小生成树 n个点连通一定是n - 1 条边 这也是连通性判断的一个依据
if(cnt < n - 1) puts("impossible");
else printf("%d\n", res); 对于Kruskal算法而言 可以只求前一半 - 最小生成森林 / 后一半 - 缩点的最小生成树 都是可以的；
有这样两个性质： - 最小生成树的边数一定是n - 1 - 得到的解不仅是边权和最小，最大边权也最小
5. 二分图
二分图这一块有判断是否是二分图（染色法） 和 二分图的最大匹配（匈牙利算法）两块；
具体细分而言
最小点覆盖 最大独立集 最小路径点覆盖 最小路径重复点覆盖问题
公式：最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径覆盖
1. 染色法判断二分图
一个图是二分图 等价于 图中没有奇数环
染色法判断二分图的实质就是DFS；一个边连接的两个点不会是同一个颜色
0 - 未染色 1 - 颜色1 2 - 颜色2
Copy bool is_bi_graph()
{
for(int i = 1; i <= n; i++)
if(!color[i])
if(!dfs(i, 1)) return false;
return true;
}
bool dfs(int a, int c)
{
color[a] = c;
for(int i = h[a]; ~i; i = ne[i])
{
int j = e[i];
if(!color[j])
{
if(!dfs(j, 3 - c)) return false;
}
else if (color[j] == c) return false;
}
return true;
}
2. 二分图的最大匹配-匈牙利算法
这个要好好背一下；
Copy int n1, n2; // n1 表示第一个集合中的点数 n2 表示第二个
int h[N], e[M], ne[M], idx; // 匈牙利算法只用存集合1到集合2的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点
bool st[N]; // 存储第二个集合中的每个点是否被当前点遍历过
bool find(int x)
{
for(int i = h[x]; ~i; i = ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
if(match[j] == 0 || find(match[j])) // j还未匹配 或者 之前匹配的可以匹配其他人
{
match[j] = x;
return true;
}
}
}
return false;
}
int res = 0;
for(int i = 1; i <= n1; i++)
{
memset(st, false, sizeof st);
if(find(i)) res++;
} 3. 最小路径重复点覆盖问题
方法：
原图的最小路径重复点覆盖 = 新图的最小路径覆盖 = 新图的 n - 最大匹配
Copy #include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
// 传递闭包
const int N = 210, M = 30010;
int n, m;
bool g[N][N], st[N];
int match[N];
bool find(int x)
{
for(int i = 1; i <= n; i++)
{
if(g[x][i] && !st[i])
{
st[i] = true;
if(match[i] == 0 || find(match[i]))
{
match[i] = x;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
while(m--)
{
int a, b;
scanf("%d%d", &a, &b);
g[a][b] = true;
}
// 传递闭包
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
g[i][j] = g[i][j] || (g[i][k] && g[k][j]);
int res = 0;
// 拆点 * 不必了 g直接当成 x -> x'
for(int i = 1; i <= n; i++)
{
memset(st, false ,sizeof st);
if(find(i)) res++;
}
cout << n - res << endl;
return 0;
} 6. 差分优化
...
7. 最近公共祖先（LCA)
LCA问题：在一个有根树中，最近的公共祖先（自己也算）
1. 倍增法
方法如下：
预处理：fa[i, j]表示从i开始 向上走2^j步所到达的节点
查询： 求lca(a, b)
保证在同一层下，共同向上跳，直到跳到LCA的下面一层
大概的框架就是这样，此外在代码实现上还有许多细节（比如哨兵节点0的应用等等）
depth显然用dfs bfs都可以，而fa[i,j] 可以用递推求解 fa[i, j] = fa[fa[i, j - 1], j - 1] （爸爸的爸爸是爷爷）
倍增法求LCA的复杂度：预处理o(nlogn) 查询一次：o(logn)
Copy int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16]; // 这里16是 log(最大深度)
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 预处理深度 -> dfs bfs都行
void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
// 哨兵节点 0 指代所有空集的情况
depth[0] = 0, depth[root] = 1;
queue<int> q;
q.push(root);
while(q.size())
{
int t = q.front();
q.pop();
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(depth[j] > depth[t] + 1)
{
q.push(j);
depth[j] = depth[t] + 1;
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--)
{
// 哨兵的好处1假如跳出去了，那么depth[a][k] = 0 < depth[b]
if(depth[fa[a][k]] >= depth[b])
a = fa[a][k];
}
if(a == b) return a;
for(int k = 15; k >= 0; k--)
{
// 哨兵的好处2假如两个点都跳出去，那么f[a][k] = f[b][k] = 0 ，就不会执行。
// 此外 跳到同一层不能判断是最近祖先（可能比LCA还高) 所以要到下一层才行
if(fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
} 2. Tarjan 离线求LCA
Copy int n, m;
int h[N], e[M], w[M], ne[M], idx;
int p[N]; // 并查集
int res[N]; // 查询返回值
int st[N]; // tarjan 保留编号
vector<PII> query[N]; // first 是查询的第二个点 second 是查询的编号
int find(int x)
{
if(p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void tarjan(int u)
{
st[u] = 1;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!st[j])
{
tarjan(j);
p[j] = u;
}
}
// 回溯
for(auto item : query[u])
{
int y = item.first, id = item.second;
if(st[y] == 2)
{
int anc = find(y); // 找到并查集的root 即为u 和 y的LCA
}
}
st[u] = 2;
}
// 把query 存储起来
int a, b;
if(a != b)
{
query[a].emplace_back(b, i);
query[b].emplace_back(a, i);
}
tarjan(...)； 8. 连通分量
1. 有向图的强连通分量
tarjan缩点
Copy int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, sz[N];
void tarjan(int u)
{
low[u] = dfn[u] = ++timestamp;
stk[++top] = u, in_stk[u] = true;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if(in_stk[j])
{
low[u] = min(low[u], dfn[j]);
}
}
// u是该强连通分量的top
if(dfn[u] == low[u])
{
int y;
++scc_cnt;
do
{
y = stk[top--];
in_stk[y] = false;
id[y] = scc_cnt;
sz[scc_cnt]++;
}while(y != u);
}
}
// 在外面
for(int i = 1; i <= n; i++)
{
if(!dfn[i])
tarjan(i);
} 此外 还有些额外的结论
设DAG的入度为0点数量为p 出度为0点的数量为q 则使得整个图为强连通量 最少需要添加的边数为max(p, q)
2. 无向图的双连通分量
无向图的双连通分量分为两种：
1. 边的双连通分量问题
和有向图的强连通分量求法类似，也是引入一个时间戳的概念 维护dfn 和 low两个时间戳数组
如何找到桥？ x -> y dfn[x] < low[y]
如何找到所有边的双连通分量？ 用一个栈帮助找到连通分量内的所有点
桥(割边) 对于一个无向连通图来说, 如果我们删除一条边之后, 图变得不再连通了, 那么我们九讲这条边称为桥.
定义 一个极大的(图中不存在任何一个非连通块中的点加入连通块之后, 该连通块依然是连通块)不包含桥的连通块
性质 对于一个边连通分量来说, 我们不管删除连通分量的哪一条边, 它都是连通的. 对于一个边连通分量来说, 任意两点之间至少包含两条不相交的路径(两条路径上无公共边) 这是一个充要条件
tarjan算法求边双连通分量
无向图不存在横叉边
因为双向不存在后面能到前面, 前面不能到后面的情况, 那么如果存在后面连到前面的一条边, 那么dfs序遍历的时候, 我们就已经将后面的点遍历到了, 就不可能再后面再遍历到后面那个点了.
时间戳 dfn[u]: 遍历到当前节点的编号 low[u]: 不经过走过来的那条边(父边)能走到的最小编号节点
判断桥 对于x, y之间的一条边, 如果low[y]能到x的祖先节点, 那么就不是桥, 若low[y] = y, 即是桥 dfn[x]<low[y](严格小于)
找e-dcc代码思路:
用栈存储搜到的所有点, 当搜到一个点的dfn[x] == low[x], 即这个点上面的一条边就为桥, 将栈中所有点标记即可
找e-dcc代码模板:
Copy void tarjan (int u, int f) // f是u这个点由哪条边过来的, 哪条边的序号
{
dfn[u] = low[u] = ++ timestamp;
st[++ tt] = u;
for(int i = h[u] ; ~i ; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j, i);
low[u] = min(low[u], low[j]);
if(dfn[u] < low[j]) // 等于也不是桥
is_bridge[i] = is_bridge[i ^ 1] = 1; // 蓝书位运算的操作
}
else if(i != f ^ 1) // 不经过父边 必定不是桥 是边连通分量, 无需判重数组
low[u] = min(low[u], dfn[j]);
}
if(dfn[u] == low[u]) // 第一个非边双连通分量中的点是入了栈的
{
int y;
dcc_cnt ++ ;
do
{
y = st[tt -- ];
id[y] = dcc_cnt;
}while(y != u);
}
} 2. 点的双连通分量问题
点双连通分量
割点 每一个割点都至少属于两个连通分量 对于一个无向连通图来说, 如果我们删除某个点之后, 该连通图不连通了, 那么我们就称其为该联通图的割点.
定义 一个极大的不包含割点的连通块 tarjan算法求点双连通分量
时间戳 dfn[u]: 意义同边双连通分量 low[u]: 每个顶点在不经过父节点的情况下能到的最小编号顶点, 如果low[u]大于等于dfn[father] (就是不能到已经遍历过的点, 即father的祖先节点), father为割点.
判断(找)割点
Copy // cc_cnt: 连通分量的数量, 而非点双
void tarjan(int u) // 找割点和所有连通分量(找子连通分量, 这种找法补不重不漏)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u;
if (u == root && h[u] == -1) // 无边节点, 单点v-dcc
{
cc_cnt ++ ;
cc[cc_cnt].push_back(u);
return;
}
int cnt = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
if (dfn[u] <= low[j]) // 对于根节点来说, 这个是必然满足的 把所有以u为根节点的子连通块全部存下来 不能不通过这个点到u的祖先节点, 则u就是这个连通分量的割点
{
cnt ++ ; // 儿子数量
if (u != root || cnt > 1) cut[u] = true; // 1. 不是根节点, 2. 是根节点, 要有两个儿子才是割点
++ cc_cnt; // 我们待会儿通过连通块中割点的个数判断点双连通分量
int y;
do
{
y = stk[top -- ];
cc[cc_cnt].push_back(y);
} while (y != j); // 如果写成y != u, 由于一个点可能属于多个v-dcc, 则u被第一个cc弹出之后, 后面的cc就永远没有u这个点了就会死循环. (后面单独加上)
cc[cc_cnt].push_back(u); // u点也是该cc的一部分
}
}
else low[u] = min(low[u], dfn[j]); // 无需vis判重数组的原因: 由于在有向图的强连通分量中, u能走到的点, 不一定是属于该SCC(因为该点不一定就能到u), 只有在栈中的才属于, 而无向图能走到的点就一定属于当前连通块
}
}
void find ()
{
for (int i = 1; i <= cc_cnt; i ++ )
{
int cnt = 0;
for (int j = 0; j < cc[i].size(); j ++ )
if (cut[cc[i][j]]) // 割点数组
cnt ++ ;
if (cnt == 0) // 割点为0就是v-dcc
{
cout << i << endl;
}
else puts("No V-dcc");
}
}
9. 欧拉回路与欧拉路径
算法会简单一些hhh
背景：哥尼斯堡七桥问题 / 一笔画问题
欧拉路径 给定一张无向图，若存在一条从节点 S 到节点 T 的路径，恰好不重不漏地经过每条边一次(可以重复经过图中的节点)，则称该路径为 S 到 T 的欧拉路。
欧拉回路 若存在一条从节点 S 出发的路径，恰好不重不漏地经过每条边一次(可以重复经过图中的节点)，最终回到起点 S，则称该路径为欧拉回路。
定义一下：
判断依据 ：
对于无向图，所有边都是连通的
存在欧拉路径的充分必要条件：度数为奇数的点只能有0 or 2个
存在欧拉回路的充分必要条件：度数为奇数的点只能有0个
对于有向图，所有边都是连通的
存在欧拉路径的充分必要条件：
要么除了两个点之外，所有点的出度等于入度，并且满足剩下的两个点 ：一个出度比入度多1（起点）一个入度比出度多1（终点）
存在欧拉回路的充分必要条件：所有点的出度均等于入度
求欧拉回路 注意这里的删边优化
Copy #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 400010;
int type;
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];
int ans[M], cnt;
int din[N], dout[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
for (int &i = h[u]; ~i;)
{
if (used[i])
{
i = ne[i];
continue;
}
used[i] = true;
if (type == 1) used[i ^ 1] = true;
int t;
if (type == 1)
{
t = i / 2 + 1;
if (i & 1) t = -t;
}
else t = i + 1;
int j = e[i];
i = ne[i];
dfs(j);
ans[ ++ cnt] = t;
}
}
int main()
{
scanf("%d", &type);
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
if (type == 1) add(b, a);
din[b] ++ , dout[a] ++ ;
}
if (type == 1)
{
for (int i = 1; i <= n; i ++ )
if (din[i] + dout[i] & 1)
{
puts("NO");
return 0;
}
}
else
{
for (int i = 1; i <= n; i ++ )
if (din[i] != dout[i])
{
puts("NO");
return 0;
}
}
for (int i = 1; i <= n; i ++ )
if (h[i] != -1)
{
dfs(i);
break;
}
if (cnt < m)
{
puts("NO");
return 0;
}
puts("YES");
for (int i = cnt; i; i -- ) printf("%d ", ans[i]);
puts("");
return 0;
} 输出字典序最小的路径 : 按照字典序来搜