图论(基础篇)

本篇内容属于图论基础篇内容，省去了最基础的概念，对于一些容易遗忘的概念和重要的基础算法做了梳理

图相关概念

连通图和连通分量

连通图：若图中任意两个顶点都连通，则称为连通图，否则称为非连通图
无向图G中的极大连通子图称为G的连通分量。任何连通图的连通分量只有一个，非连通图有多个连通分量

强连通图和强连通分量

有向图：若从定点i到顶点j有路径，则称从顶点i到j是连通的。若图G中任意两个顶点i和j都连通，即从顶点i到j和从顶点j到i都存在路径，则称图G是强连通图
有向图G中的极大强连通子图称为G的强连通分量。非强连通图有多个强连通分量。

图的存储

邻接矩阵存储

定义

邻接矩阵时表示顶点之间相邻关系的矩阵。设G=（V, E）是具有n(n > 0)个顶点的图，顶点的编号依次为0 ~ n - 1

无向图中若(i, j) 连通：A[i] [j] = 1
有向图中若i到j有边：A[i] [j] = 1
带权无向图，A[i] [j] = w_ij
带权有向图，A[i] [j] = w_ij

存储类型

使用二维数组来进行存储

特点

邻接矩阵唯一
适合稠密图的存储

邻接表存储

每个单链表上添加一个表头节点（表示顶点信息）。并将所有表头节点构成一个数组，下标为i的元素表示顶点i的表头节点

存储类型

使用vector边长数组来存

若只用存储重点编号，则可以直接定义为int类型 vector <int> Adj[N]

vector<int> Adj[N];
// 添加一条从1号顶点到达3号顶点的有向边
Adj[1].push_back(3);

若要存储重点编号和边权，那么可以使用结构体Node来存储

struct Node {
    int v;	// 边的终点编号
    int w;	// 边权
    Node (int _v, int _w) : v(_v), w(_w) {}		// 构造函数
}

vector<Node> Adj[N];
// 添加一条从1号顶点到达3号顶点的有向边，边权为4
Adj[1].push_back(Node(3, 4));

图的遍历

图的遍历这一部分一定要熟记DFS和BFS的算法模板，很多题目就是在这些模板上做一些处理就可以解决

深度优先搜索 DFS

邻接矩阵存储遍历

节点编号为 1 ~ n

const int INF = 0x3f3f3f3f;
// 邻接矩阵存储图的信息g[i][j]表示顶点 i 到顶点 j 这条边的权值大小
int g[N][N];
bool st[N];
// 初始化
memset(g, 0x3f, sizeof g);

void dfs(int u) {
    // 先标记这个点已经被访问过
    st[u] = true;
    // 递归地去遍历和该点连通的点
    for (int i = 1; i <= n; i++) {
        if (!st[i] && g[u][i] != INF)
            dfs(i);
    }
}

邻接表存储遍历

节点编号为 1 ~ n

// 使用邻接表来存储图
vector<int> g[N];
bool st[N];

void dfs(int u) {
    // st[u] 表示点u已经被遍历过
    st[u] = true;
	// 递归地去遍历和该点连通的点
    for (int i = 0; i < g[u].size(); i++) {
        if (!st[g[u][i]]) 
            dfs(g[u][i]);
    }
}

广度优先搜索 BFS

邻接矩阵存储遍历

节点编号为 1 ~ n

const int INF = 0x3f3f3f3f;
// 邻接矩阵存储图的信息g[i][j]表示顶点 i 到顶点 j 这条边的权值大小
int g[N][N];
bool st[N];
// 初始化
memset(g, 0x3f, sizeof g);

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (!q.empty()) {
    int t = q.front();
    q.pop();
    
    for (int i = 1; i <= n; i++) {
        if (!st[i] && g[t][i] != INF) {
            st[i] = true; // 表示点i已经被遍历过
            q.push(i);
        }
    }
}

最短路径

Dijkstra算法

Dijkstra算法用来解决单源最短路问题，不存在负边权，给定图G和起点s，通过算法得到S到其他任何顶点的最短距离

朴素Dijkstra

dist[1] = 0, dist[i] = MAX;
集合S：当前已确定最短距离的点

for i : 1 ~ n
	不在集合S中，距离最近的点  --> t;
	t  --> 集合S
	用t更新其他点的距离 (当dist[x] > dist[t] + w 就更新dist[x])

代码模板

/**
 * @file Dijkstra.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-06-07 18:10:32
 * @brief Dijkstra算法
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int N = 510;

int n, m;
// 使用邻接矩阵来存储
int g[N][N];
// 保存最短距离
int dist[N];
// 用来判断是否有加入到集合中
bool st[N];

int dijkstra() {
    // 先初始化为正无穷
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        // 找到不在集合S中距离最近的点
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        // 将t加入到集合
        st[t] = true;
        // 用t来更新其他点距离
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if (dist[n] == 0x3f3f3f3f)
        return -1;
    return dist[n];
}

堆优化版Dijkstra

核心思想：集合中找最近的点的操作可以使用堆来实现，C++中可以使用优先队列priority_queue来实现

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
const int N = 1000010;
// 第一个存放边权，第二个存放节点编号(方便heap按边权排序)
typedef pair<int, int> PII;

int n, m;
// 使用邻接表来存储
vector<PII> g[N];

// 保存最短距离
int dist[N];
// 用来判断是否有加入到集合中
bool st[N];

int dijkstra() {
    // 先置为正无穷
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 使用小根堆
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    // pair排序时是先根据first，再根据second，这里显然要根据距离排序
    heap.push({0, 1});
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if (st[ver])
            continue;
        st[ver] = true;
        
        // 更新节点
        for (int i = 0; i < g[ver].size(); i++) {
            int j = g[ver][i].second;
            if (dist[j] > dist[ver] + g[ver][i].first) {
                dist[j] = dist[ver] + g[ver][i].first;
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f)
        return -1;
    return dist[n]; 
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // a到b之间有一条边权为c的边
        g[a].push_back({c, b});
    }
    
    int t = dijkstra();
    printf("%d\n", t);
    return 0;
}

Bellman-Ford算法

适合存在负边权的最短路，而且最短路不一定存在（例如存在负权回路）

for 1 ~ n
	for 所有边 a, b, w
		dist[b] = min(dist[b], dist[a] + w);

求有边数限制的最短路

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。

注意：图中可能 存在负权回路 。

输入格式

第一行包含三个整数n，m，k。

接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式

输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。

如果不存在满足条件的路径，则输出“impossible”。

数据范围

1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过10000。

输入样例：

输出样例：

/**
 * @file Bellman-Ford.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-07-08 21:30:56
 * @brief Bellman-Ford算法求有边数限制的最短路
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];

struct Edge {
    int a;
    int b;
    int w;
} edge[M];

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < k; i++) {
        // 做数组拷贝，防止在下面的更新操作中被串联更新
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m; j++) {
            auto e = edge[j];
            dist[e.b] = min(dist[e.b], backup[e.a] + e.w);
        }
    }
    // 这里不直接写等于无穷：是因为有可能距离无穷的那个节点在里层的for循环会更新下一个无穷的节点
    if (dist[n] > 0x3f3f3f3f / 2)
        return -1;
    else
        return dist[n];
}

int main() {

    cin >> n >> m >> k;
    // 读入m条边
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edge[i] = {a, b, w};
    }

    int t = bellman_ford();
    if (t == -1)
        cout << "impossible" << endl;
    else
        cout << t << endl;
    return 0;
}

SPFA算法

spfa求最短路算法其实是对Bellman-Ford算法改进，在Bellman-Ford算法中dist[b] = min(dist[b], dist[a] + w);，如果dist[a]没有变小，那么这个操作一定会是无效的操作，spfa算法就是在这里利用BFS进行优化

queue <-- 1;
while queue 不空
	t = q.front();
	q.pop();
	更新t的所有出边(如果被更新，就再加到队列去更新别人)

SPFA求最短路

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式

输出一个整数，表示1号点到n号点的最短距离。

如果路径不存在，则输出”impossible”。

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过10000。

输入样例：

输出样例：

/**
 * @file SPFA.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-07-08 21:07:47
 * @brief SPFA算法求最短路
 *          在Bellman-Ford算法中dist[b] = min(dist[b], dist[a] + w);
 *          如果dist[a]没有变小，那么这个操作一定会是无效的操作
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int N = 100010;
// 第一个位置存储编号，第二个位置存储边权
typedef pair<int, int> PII;

int n, m;
vector<PII> g[N];
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;
    // 利用BFS的思想优化Bellman-Ford算法就是SPFA
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = 0; i < g[t].size(); i++) {
            int j = g[t][i].first;
            int w = g[t][i].second;
            // 队列中存的就是那些变小的节点：更新过谁，我再拿谁更新别人
            if (dist[j] > dist[t] + w) {
                dist[j] = dist[t] + w;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        // 加一条从a到b的边，边权为c
        g[a].push_back({b, c});
    }

    int t = spfa();

    if (t == 0x3f3f3f3f)
        cout << "impossible" << endl;
    else
        cout << t << endl;

    return 0;
}

SPFA判断负环

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式

如果图中存在负权回路，则输出“Yes”，否则输出“No”。

数据范围

1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过10000。

输入样例：

输出样例：

Yes

更新dist[x]时候，同时记录cnt[x]，记录每个节点最短路的边数 cnt[x] >= n 表示经过了n + 1个点，说明有环的存在

/**
 * @file SPFA-hasCircle.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-07-08 22:28:12
 * @brief SPFA判断回路里面是否有负环
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 2010, M = 10010;
typedef pair<int, int> PII;

int n, m;
vector<PII> g[N];
int dist[N];
// 记录最短路的边数，cnt[x] >= n 表示有环
int cnt[N];
bool st[N];

bool spfa() {
    queue<int> q;
    // 将所有点都入队：因为以前只是求固定一个点
    // 但存在负权回路的时候，不一定所有点都能经过负权回路
    for (int i = 1; i <= n; i++) {
        st[i] = true;
        q.push(i);
    }
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        // 出队了进行标记，没有在队列里面
        st[t] = false;

        for (int i = 0; i < g[t].size(); i++) {
            int j = g[t][i].first;
            int w = g[t][i].second;
            // 当前需要更新
            if (dist[j] > dist[t] + w) {
                dist[j] = dist[t] + w;
                cnt[j] = cnt[t] + 1;
                // 最短路的边数 >= n 表示存在环
                if (cnt[j] >= n)
                    return true;
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }

    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }

    if (spfa())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Floyd算法

对于一个各边权值均大于零的有向图，对于每一个顶点 i ≠ j，求出顶点i与顶点j之间最短路径和最短路径长度

/**
 * @file Floyd.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-06-30 00:42:40
 * @brief Floyd算法：多源最短路算法：动态规划思想
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 210;

int n, m;
// d[i][j] 存储所有边，执行完floyd算法存的就是i到j的最短距离
int d[N][N];

// 求多源汇最短路floyd算法
void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                // 上一层：从i出发只经过i ~ k - 1 到j的距离
                // d[i][k] + d[k][j] 经过k的距离
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

最小生成树

对于带权连通图G（每条边上的权值为大于零的实数），可能有多颗不同的生成树

每棵生成树的所有边的权值之和可能不同

其中权值之和最小的生成树称为图的最小生成树

Prim算法(适合稠密图)

给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。

输入格式

第一行包含两个整数n和m。

接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

数据范围

1≤n≤500,
1≤m≤10^5,
图中涉及边的边权的绝对值均不超过10000。

输入样例：

输出样例：

核心思想：让一棵小树长大
从顶点开始，找距离树最近的边的点加进来（贪心思想）
从未加到树中的顶点选一个距离树最小距离的点加进来，直到所有点都加进来
时间复杂度O(n^2)

S：当前连通块的点集
dist[i]:表示点i到最集合的距离

dist初始化为正无穷
for 1 ~ n
	t = 集合外距离最近的点
	用 t 来更新其他点到集合的距离

/**
 * @file Prim.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-06-29 22:02:16
 * @brief Prim算法
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 510;
const int M = 100010;
const int INF = 0x3f3f3f3f;

int n, m;
int dist[N];
bool st[N];
int g[N][N];

int prim() {
    // prim算法中dist[j]表示当前点到集合的距离
    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;
        }
        st[t] = true;
        // 不是第一个点且dist[t]为正无穷的情况,说明没有找到
        if (i != 0 && dist[t] == INF)
            return INF;
        // 放在前面，防止有环的出现
        if (i != 0)
            res += dist[t];
        // 用t更新其他点到集合的距离
        for (int j = 1; j <= n; j++) {
            // Dijkstra算法找的是距起点的距离
            // Prim算法找的是距离集合的距离
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();
    if (t == INF)
        cout << "impossible" << endl;
    else
        cout << t << endl;

    return 0;
}

Kruskal算法(适合边稀疏图)

给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。

输入格式

第一行包含两个整数n和m。

接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

数据范围

1≤n≤10^5,
1≤m≤2∗10^5,
图中涉及边的边权的绝对值均不超过1000。

输入样例：

输出样例：

核心思想：将森林合并成树
将所有边从小到大排序（最慢的一步O(mlog m)）
枚举每一条边，a -> b，权重c，a和b不连通，将这条边加到集合当中(并查集)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n ,m;
int p[N];

struct Edge {
    int a, b, w;
    // 重载小于号，方便排序
    bool operator< (const Edge& e) const {
        return w < e.w;
    }
}edges[N];

// 并查集找祖宗节点
int find(int x) {
    if (p[x] != x) 
        p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    // 对边按权值大小排序
    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 = edges[i].a;
        int b = edges[i].b;
        int w = edges[i].w;
        
        // 找是否在一个集合中
        a = find(a);
        b = find(b);
        
        // 没有在一个集合当中，要再a和b之间加一条边, 边权已经排序，直接加入权值
        if (a != b) {
            p[a] = b;
            res += w;
            cnt++;
        }
    }
    
    if (cnt < n - 1)
        cout << "impossible" << endl;
    else
        cout << res << endl;
    return 0;
}

拓扑排序

对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。

输入格式

第一行包含两个整数 NN 和 MM，分别表示有向图的点和边的数量。

接下来 MM 行，每行给出一条边的起点和终点。

点的编号从 11 到 NN。

再一行包含一个整数 KK，表示询问次数。

接下来 KK 行，每行包含一个所有点的排列。

一行中的数字用空格隔开。

输出格式

在一行中输出所有不是拓扑序列的询问序列的编号。

询问序列编号从 00 开始。

行首和行尾不得有多余空格，保证存在至少一个解。

数据范围

1≤N≤1000,
1≤M≤10000,
1≤K≤100

输入样例：

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

输出样例：

3 4

/**
 * @file Test.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-06-14 21:11:37
 * @brief 判断拓扑排序
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

const int N = 1010, M = 10010;
struct Edge {
    int a;
    int b;
} e[M];
int n, m;
// 记录路径中的下标
int pos[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        e[i].a = a;
        e[i].b = b;
    }

    int k;
    cin >> k;
    vector<int> res;
    for (int i = 0; i < k; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            pos[x] = j;
        }

        bool success = true;
        for (int j = 0; j < m; j++) {
            if (pos[e[j].b] < pos[e[j].a]) {
                success = false;
                break;
            }
        }
        if (!success)
            res.push_back(i);
    }
    if (res.size() > 0) {
        cout << res[0];
        for (int i = 1; i < res.size(); i++)
            cout << ' ' << res[i];
    }
    return 0;
}

特殊图

二分图

二分图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说**：把一个图的顶点划分为两个不相交子集，使得每一条边都分别连接两个集合中的顶点。如果存在这样的划分，则此图为一个二分图**

染色法判定二分图

充要条件：一个图是二分图当且仅当图中不含奇数环
判定是否是一个二分图：染色法

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
int color[N];

bool dfs(int u, int c) {
    color[u] = c;
    // 遍历所有的点
    for (int i = 0; i < g[u].size(); i++) {
        int j = g[u][i];
        // 没有染色就去dfs染色
        if (!color[j]) {
            // 递归调用：1变2, 2变1的过程
            if (!dfs(j, 3 - c))
                return false;
        }
        // 染色且颜色相同，就表示不是二分图
        else if (color[j] == c)
            return false;
    }
    
    return true;
}

int main() {
    cin >> n >> m;
    
    while (m--) {
        int a, b;
        cin >> a >> b;
        // 无向图：两条边都要加
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    bool flag = true;
    for(int i = 1; i <= n; i++) {
        // 该点没有染色，就开始dfs开始染色
        if (!color[i]) {
            if (!dfs(i, 1)) {
                flag = false;
                break;
            }
        }
    }
    
    if (flag) 
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
}

匈牙利算法求二分图最大匹配

给定一个二分图，其中左半部包含n1个点（编号1_{n1），右半部包含n2n2个点（编号1}n2），二分图共包含m条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

输入格式

第一行包含三个整数 n1、 n2和 m。

接下来m行，每行包含两个整数u和v，表示左半部点集中的点u和右半部点集中的点v之间存在一条边。

输出格式

输出一个整数，表示二分图的最大匹配数。

数据范围

1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤10^5

输入样例：

输出样例：

如何理解匈牙利算法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 510;

int n1, n2, m;
vector<int> g[N];
bool st[N];
// match[j]表示右边集合匹配左边集合点的编号
int match[N];

bool find(int x) {
    
    for(int i = 0; i < g[x].size(); i++) {
        int j = g[x][i];
        if (!st[j]) {
            st[j] = true;
            // 当没有任何匹配的时候或者匹配到左边集合的点可以匹配到别的节点
            if (match[j] == 0 || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    cin >> n1 >> n2 >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        // 只用存一条有向边
        g[a].push_back(b);
    }
    
    int res = 0;
    
    // 只用枚举左边的集合
    for (int i = 1; i <= n1; i++) {
        // 每次都要清空：目的是针对左边不同的节点我们需要尝试去匹配所有和他相连的节点，即使匹配的节点已经被匹配过
        memset(st, false, sizeof st);
        if (find(i))
            res++;
    }
    
    cout << res << endl;
    
    return 0;
}

欧拉图

欧拉路径是图中的一条路径，该路径满足恰好访问每个边一次
欧拉回路是一条在同一顶点处开始和结束的欧拉路径
如果一个连通图的所有顶点的度数都为偶数，那么这个连通图具有欧拉回路，且这个图被称为欧拉图
如果一个连通图中有两个顶点的度数为奇数，其他顶点的度数为偶数，那么所有欧拉路径都从其中一个度数为奇数的顶点开始，并在另一个度数为奇数的顶点结束
具有欧拉路径但不具有欧拉回路的图被称为半欧拉图

欧拉路径

输入格式
第一行包含两个整数 N 和 M，表示无向图的点和边的数量。

接下来 M 行，每行包含两个整数 a,b，表示点 a 和 b 之间存在一条边。

所有点的编号从 1∼N。

输出格式
首先，在第一行按顺序输出点 1∼N 中每个点的度数。

第二行输出对该图的判断，Eulerian（欧拉图），Semi-Eulerian（半欧拉图），Non-Eulerian（非欧拉图）。

行尾不得有多余空格。

#include <iostream>
#include <cstring>

using namespace std;
const int N = 510;

int n, m;
//
bool g[N][N];
// 记录每个点的度数
int d[N];
bool st[N];

// dfs遍历所有点，返回点的个数
int dfs(int u) {
    st[u] = true;
    
    // 先将自己计算，所以置为1
    int res = 1;
    for (int i = 1; i <= n; i++) {
        if (!st[i] && g[u][i])
            res += dfs(i);
    }
    
    return res;
}

int main() {
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
        d[a]++;
        d[b]++;
    }
    
    int cnt = dfs(1);
    cout << d[1];
    
    for (int i = 2; i <= n; i++)
        cout << ' ' << d[i];
    cout << endl;
    
    if (cnt == n) {
        int s = 0;
        for (int i = 1; i <= n; i++) 
            if (d[i] % 2)
                s++;
        if (s == 0)
            cout << "Eulerian" << endl;
        else if (s == 2)
            cout << "Semi-Eulerian" << endl;
        else
            cout << "Non-Eulerian" << endl;
        
    }else
        cout << "Non-Eulerian" << endl;
    return 0;
}

哈密顿图

哈密顿回路问题是包含图中每个顶点的简单回路
哈密顿图是一个无向图，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）

哈密顿回路

哈密顿回路问题是找到一个包含图中每个顶点的简单回路。

这样的回路称为“哈密顿回路”。

在本题中，你需要做的是判断给定路径是否为哈密顿回路。

输入格式

第一行包含一个整数 N 表示顶点数，一个整数 M 表示给定无向图中的边数。

接下来 M 行，每行包含两个整数 a,b，表示点 a和 b之间存在一条边。

所有顶点编号从 1 到 N。

再一行给出整数 KK，表示询问次数。

接下来 KK 行，每行包含一个询问，格式如下：

n V1 V2 … Vn

n 表示给定路径经过的点的数目，Vi 是路径中经过的点。

输出格式

对于每个询问，如果是哈密顿回路则在一行输出 YES，否则输出 NO。

数据范围

2<N≤200,
N−1≤M≤N(N−1)/2,
1≤K≤1000,
1≤n≤410

输入样例：

6 10
6 2
3 4
1 5
2 5
3 1
4 1
1 6
6 3
1 2
4 5
6
7 5 1 4 3 6 2 5
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 3 4 5 2 6
7 6 1 2 5 4 3 1

输出样例：

YES
NO
NO
NO
YES
NO

#include <iostream>
#include <cstring>

using namespace std;
const int N = 210;

bool g[N][N];
int n, m;
bool st[N];
int nodes[N * 2];

bool check(int cnt) {
    // 起点和终点不一样或者点数小于n + 1
    if (nodes[0] != nodes[cnt - 1] || cnt != n + 1)
        return false;
    memset(st, 0, sizeof st);
    for (int i = 0; i < cnt - 1; i++) {
        st[nodes[i]] = true;
        // 边不存在
        if (!g[nodes[i]][nodes[i + 1]])
            return false;
    }
    // 所有点都走到了
    for (int i = 1; i <= n; i++) {
        if (!st[i])
            return false;
    }
    
    return true;
}


int main() {
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
    }
    int k;
    cin >> k;
    while (k--) {
        int cnt;
        cin >> cnt;
        for (int i = 0; i < cnt; i++) {
            cin >> nodes[i];
        }
        
        if (check(cnt))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    } 
}

补充

数组模拟链表

e[N]：存储节点值value
ne[N]：存储某个节点的next指针
head表示头结点的下标
idx表示已经用到了哪个点

/**
 * @file LinkList.cpp
 * @author Rick (Kay_Rick@outlook.com)
 * @version 1.0
 * @date 2020-06-07 19:36:30
 * @brief 数组模拟链表实现
 * 
 * @copyright Copyright (c) 2020 Rick, All Rights Reserved.
 * 
 */

#include <iostream>
using namespace std;

const int N = 100010;

// head表示头结点的下标
// e[i]表示节点i的值
// ne[i]表示节点i的next指针是多少
// idx表示已经用到了哪个点
int e[N], ne[N], idx, head;

void init () {
    head = -1;
    idx = 0;
}

/**
 * @brief 将x插到头结点
 * @param x 
 */
void add_to_head (int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

/**
 * @brief 将节点 x 插入到下标为 k 的节点的后面
 * @param k 
 * @param x 
 */
void add (int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

/**
 * @brief 将下标是k的点后面的点删除
 * @param k 
 */
void remove (int k) {
    ne[k] = ne[ne[k]];
}

树与图的存储

树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a] [b] 存储边a->b

(2) 邻接表：可以使用vector来存储 vector <int> g[N]

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边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);

并查集

解决什么问题

将两个集合合并
询问两个元素是否在一个集合当中

基本原理

每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点

如何判断树根？
```
if (p[x] == x)
```

如何求x的集合编号？

while (p[x] != x)
    x = p[x];

优化：路径压缩，第一次求祖先节点的时候把所有遍历的点的父节点都设为祖先节点

// 返回x的祖宗节点 + 路径压缩
int find (int x) {
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

如何合并两个集合？

// p[x]是x的集合编号，p[y]是y的集合编号
p[x] = y;

图论(基础篇)

图相关概念

连通图和连通分量

强连通图和强连通分量

图的存储

邻接矩阵存储

定义

存储类型

特点

邻接表存储

存储类型

图的遍历

深度优先搜索 DFS

邻接矩阵存储遍历

邻接表存储遍历

广度优先搜索 BFS

邻接矩阵存储遍历

最短路径

Dijkstra算法

朴素Dijkstra

堆优化版Dijkstra

Bellman-Ford算法

求有边数限制的最短路

SPFA算法

SPFA求最短路

SPFA判断负环

Floyd算法

最小生成树

Prim算法(适合稠密图)

Kruskal算法(适合边稀疏图)

拓扑排序

特殊图

二分图

染色法判定二分图

匈牙利算法求二分图最大匹配

欧拉图

欧拉路径

哈密顿图

哈密顿回路

补充

数组模拟链表

树与图的存储

并查集

解决什么问题

基本原理

感谢您的支持，我会继续努力的!