老黑2022秋季上课内容
链式前向星
关键代码
\(N\) 表示点数 + 10; \(M\) 表示边数 + 10。
有向边
初始数组
struct Edge{
int next, to, v;
/*
* next 记录上一条边同一起点的id
* to记录这条边的终点
* v记录这条边的权值(可有可无)
*/
}edge[M];
int head[N], cnt;
加边函数
void add(int x, int y, int z) {
/*
* x表示这条边的起点
* y表示这条边的终点
* z表示这条边的权值
*/
cnt++;
edge[cnt].to = y;
edge[cnt].v = z;
edge[cnt].next = head[x];
head[x] = cnt;
}
有向边
初始数组
struct Edge{
int next, to, v;
/*
* next 记录上一条边同一起点的id
* to记录这条边的终点
* v记录这条边的权值(可有可无)
*/
}edge[M << 1];
int head[N], cnt;
加边函数
void add(int x, int y, int z) {
/*
* x表示这条边的起点
* y表示这条边的终点
* z表示这条边的权值
*/
cnt++;
edge[cnt].to = y;
edge[cnt].v = z;
edge[cnt].next = head[x];
head[x] = cnt;
}
易错点
- 加边时要
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
- 初始数组时要
edge[M << 1]也就是要\(2\)倍，因为一条边要加两次
并查集
关键代码
初始变量
int father[100000];
//自己的父亲。
初始化
void init() {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}
找祖先
void find(int x) {
if(father[x] == x) return x;
else return find(father[x]);
}
合并
void merge(int x, int y) {
father[find(x)] = find(y);
}
最短路
Floyed/DP
关键代码
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
map[j][k] = min(map[j][k],map[j][i] + map[i][k]);
}
}
}
Dijkstra 单源最短路
思路
每次把最近的点加进来即可。
关键代码
while (1) {
int MIN = 0;
for (int i = 1; i <= n; i++)
if (!vis[i])
if (juli[MIN] > juli[i])
MIN = i;
if (MIN == 0) {
break;
}
vis[MIN] = 1;
for (int i = 1; i <= n; i++) {
if (!vis[i] && map[MIN][i] && juli[i] > juli[MIN] + map[MIN][i]) {
juli[i] = juli[MIN] + map[MIN][i];
}
}
}
SPFA
思路
- 先把这个源点入队
- 再把队首的连的边判断是否更近，更近即入队。
关键代码
void SPFA(int x) {
while(q.size()) q.pop();
for (int i = 1; i <= n; i++) {
dis[i] = INT_MAX;
}
dis[x] = 0;
q.push(x);
while (!q.empty()) {
int temp = q.front();
q.pop();
for (int j = 1; j <= n; j++) {
if (dis[j] > mp[temp][j] + dis[temp]) {
dis[j] = dis[temp] + mp[temp][j];
if (!vis[j]) {
q.push(j);
vis[j] = 1;
num[j]++;
}
}
}
vis[temp] = 0;
}
}
强连通分量
Kosaraju
洛谷P2863全代码
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int last;
int to;
}edge1[50005],edge2[50005];
int next1[10005], next2[10005],cnt, cnt_d,cnt_b,ans;
int d[10005];
//1正，2反
bool vis[10005];
int n, m;
void add(int x, int y) {
cnt++;
edge1[cnt].to = y;
edge1[cnt].last = next1[x];
next1[x] = cnt;
edge2[cnt].to = x;
edge2[cnt].last = next2[y];
next2[y] = cnt;
}
void dfs1(int x) {
vis[x] = 1;
for (int i = next2[x];i;i = edge2[i].last) {
if(!vis[edge2[i].to]) dfs1(edge2[i].to);
}
d[++cnt_d] = x;
}
void dfs2(int x) {
vis[x] = 0;
for (int i = next1[x];i;i = edge1[i].last) {
if(vis[edge1[i].to]) {
dfs2(edge1[i].to); cnt_b++;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
add(x,y);
}
for (int i = 1; i <= n; i++) {
if(!vis[i]) {
dfs1(i);
}
}
for (int i = n; i >= 1; i--) {
if(vis[i]) {
cnt_b = 0;
dfs2(i);
if(cnt_b > 0) ans++;
}
}
cout << ans;
}
Tarjan
关键代码
void tarjan(int x) {
dfn[x] = low[x] = ++tot;
st.push(x);
instk[x] = 1;
for (int j = head1[x]; j; j = edge1[j].nex) {
int y = edge1[j].to;
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if (instk[y])
low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x]) {
int y;
++cnt;
do {
y = st.top();
st.pop();
instk[y] = 0;
scc[y] = cnt;
} while (y != x);
}
}
缩点
割点（边） 和 桥
割点
假设DFS中我们从顶点\(U\)访问到了顶点\(V\)(此时顶点\(V\)还未被访问过），那么我们称顶点\(U\)为 顶点\(V\)的父顶点，\(V\)为\(U\)的孩子顶点。在顶点\(U\)之前被访问过的顶点，我们就称之为\(U\)的祖先顶点。
显然如果顶点\(U\)的所有孩子顶点可以不通过父顶点\(U\)而访问到\(U\)的祖先顶点，那么说明此时去掉顶点\(U\)不影响图的连通性，\(U\)就不是割点。相反，如果顶点\(U\)至少存在一个孩子顶点，必须通过父顶点\(U\)才能访问到
\(U\)的祖先顶点，那么去掉顶点\(U\)后，顶点\(U\)的祖先顶点和孩子顶点就不连通了，说明\(U\)是一个割点。
若\(x\)不是搜索树的根节点,若\(x\)节点是割点,那么当且仅当搜索树上存在\(x\)的一个儿子节点\(y\),满足\(dfn[x] \le low[y]\)。
割桥
无向边\(（x，y）\)是桥,当且仅当搜索树上存在\(x\)的一个子节点\(y\);满足
\(dfn[x]<low[y]\)