图论-JZTXT

$DFS$

$DFS$ 全称是 $Depth\ First\ Search$，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

$DFS$ 最显著的特征在于其递归调用自身。同时与 $BFS$ 类似，$DFS$ 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保每个点仅访问一次。符合以上两条规则的函数，便是广义上的 $DFS$。

该算法通常的时间复杂度为 $O(n+m)$，空间复杂度为 $O(n)$，其中 $n$ 表示点数，$m$ 表示边数。注意空间复杂度包含了栈空间，栈空间的空间复杂度是 $O(n)$ 的。在平均 $O(1)$ 遍历一条边的条件下才能达到此时间复杂度，例如用前向星或邻接表存储图；如果用邻接矩阵则不一定能达到此复杂度。

数组邻接表

void dfs(int u)
{
	st[u] = 1;
	for(int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if(!st[j])
		{
			dfs(j);
		}
	}
}

vector邻接表

void dfs(int u)
{
	st[u] = 1;
	for(int i = 0; i < e[u].size(); i ++)
	{
		int v = e[u][i], ww = w[u][i];
		if(!st[u])
		{
			dfs(v);
		}
	}
}

$DFS$序列

$DFS$ 序列是指 $DFS$ 调用过程中访问的节点编号的序列。

每个子树都对应 $DFS$ 序列中的连续一段（一段区间）。

括号序列

$DFS$ 进入某个节点的时候记录一个左括号 (，退出某个节点的时候记录一个右括号 )。

每个节点会出现两次。相邻两个节点的深度相差 $1$。

一般图上 $DFS$

对于非连通图，只能访问到起点所在的连通分量。

对于连通图，$DFS$ 序列通常不唯一。

注：树的 $DFS$ 序列也是不唯一的。

在 $DFS$ 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，称为 $DFS$ 树。$DFS$ 树是原图的一个生成树。

例1. 全排列

点击查看代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)

using namespace std;

int s[100];
bool p[100];

void dfs(int u, int fa)
{
	if(u > fa)
	{
		for(int i = 1; i <= fa; i ++)
			cout << s[i] << ' ';
		cout << '\n';
	}
	for(int i = 1; i <= fa; i ++)
	{
		if(!p[i])
		{
			s[u] = i;
			p[i] = true;
			dfs(u + 1, fa);
			p[i] = false;
			s[u] = 0;
		}
	}
}

void solve()
{
	int n;
	cin >> n;
	for(int i = 0; i <= n; i ++)
		s[i] = p[i] = 0;
	dfs(1, n);
}

signed main()
{
	IOS;
	int _ = 1;
	// cin >> _;
	while(_ --)
		solve();
	return 0;
}

例2. 八皇后

点击查看代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)

using namespace std;

int ans, a[100], b[100], n, m;
bool check(int x, int y)
{
	for(int i = 1; i <= x; i ++)
	{
		if(a[i] == y||i + a[i] == x + y||i - a[i] == x - y)
			return false;
	}
	return true;
}

void dfs(int r)
{
	if(r == n +  1)
	{
		ans ++;
		return ;
	}
	for(int i = 1; i <= n; i ++)
		if(check(r, i))
		{
			a[r] = i;
			dfs(r + 1);
			a[r] = 0;
		}
}

void init()
{
	for(n = 1; n <= 10; n ++)
	{
		ans = 0;
		dfs(1);
		b[n] = ans;
	}
}
void solve()
{
	while(cin >> m, m)
		cout << b[m] << '\n';
}

signed main()
{
	IOS; init();
	int _ = 1;
	// cin >> _;
	while(_ --)
		solve();
	return 0;
}

$BFS$

$BFS$ 全称是 $Breadth\ First\ Search$，中文名是宽度优先搜索，也叫广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

这样做的结果是，$BFS$ 算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。

在 $BFS$ 结束时，每个节点都是通过从起点到该点的最短路径访问的。

时间复杂度: $O(n + m)$

空间复杂度: $O(n)$（$vis$ 数组和队列）

数组邻接表

void bfs(int u)
{
	int hh = 0, tt = -1;
	q[++ tt] = u;
	st[u] = true;
	while(hh <= tt)
	{
		int t = q[hh ++];
		for(int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if(!st[j])
			{
				st[j] = true;
				q[++ tt] = j;
			}
		}
	}
}

vector邻接表

void bfs(int u)
{
	queue<int> q;
	q.push(u);
	st[u] = true;
	while(!q.empty())
	{
		int t = q.front();
		q.pop();
		for(int i = 0; i < e[t].size(); i ++)
		{
			int j = e[t][i];
			if(!st[j])
			{
				st[j] = true;
				q.push(j);
			}
		}
	}
}

树上问题

树的直径

树上任意两节点之间最长的简单路径即为树的「直径」。

最近公共祖先LCA

最近公共祖先简称 $LCA（Lowest Common Ancestor）$。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。为了方便，我们记某点集 $S=\{v_1,v_2,\ldots,v_n\}$ 的最近公共祖先为 $\text{LCA}(v_1,v_2,\ldots,v_n)$ 或 $\text{LCA}(S)$

例. 距离

题目描述：

给出 $n$ 个点的一棵树，多次询问两点之间的最短距离。

注意：边是无向的。所有节点的编号是 $1,2,…,n$。

输入格式:

第一行为两个整数 $n$ 和 $m$ 。$n$ 表示点数，$m$ 表示询问次数；

下来 $n−1$ 行，每行三个整数 $x,y,k$，表示点 $x$ 和点 $y$ 之间存在一条边长度为 $k$；

再接下来 $m$ 行，每行两个整数 $x,y$，表示询问点 $x$ 到点 $y$ 的最短距离。

树中结点编号从 $1$ 到 $n$。

输出格式:

共 $m$ 行，对于每次询问，输出一行询问结果。

输入1

2 2
1 2 100
1 2
2 1

输出1

100
100

输入2

3 2
1 2 10
3 1 15
1 2
3 2

输出2

10
25

数据范围

$2≤n≤10^4,1≤m≤2×10^4,0<k≤100,1≤x,y≤n$

LCA模板

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)

using namespace std;

const int N = 1e5 + 10, M = N * 2, S = 16;

int h[N], w[M], e[M], ne[M], idx;
int fa[N][S], ce[N];
int q[N], dist[N];
int n, m, root;

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void LCA_init()
{
	int hh = 0, tt = -1;
	ce[root] = 1;
	q[++ tt] = root;
	while(hh <= tt)
	{
		int t = q[hh ++];
		for(int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if(ce[j] == 0)
			{
				ce[j] = ce[t] + 1;
				dist[j] = dist[t] + w[i];
				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 query(int a, int b)
{
	if(ce[a] < ce[b]) swap(a, b);
	for(int i = 14; i >= 0; i --)
		if(ce[fa[a][i]] >= ce[b])
			a = fa[a][i];
	if(a == b) return a;
	for(int i = 14; i >= 0; i --)
		if(fa[a][i] != fa[b][i])
		{
			a = fa[a][i];
			b = fa[b][i];
		}
	return fa[a][0];
}

void solve()
{
	memset(h, -1, sizeof h);
	root = 1;
	cin >> n >> m;
	int a, b, c;
	for(int i = 1; i < n; i ++)
	{
		cin >> a >> b >> c;
		add(a, b, c), add(b, a, c);
	}
	LCA_init();
	int x, y, ans;
	while(m --)
	{
		cin >> x >> y;
		ans = dist[x] + dist[y] - 2 * dist[query(x, y)];
		cout << ans << "\n";
	}
}

signed main()
{
	IOS;
	int _ = 1;
//	cin >> _;
	while(_ --)
		solve();
	return _ ^ _;
}

树链剖分

树的层次

题目描述：

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

所有边的长度都是 $1$，点的编号为 $1∼n$。

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

输入格式:

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

接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示存在一条从 $a$ 走到 $b$ 的长度为 $1$ 的边。

输出格式:

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

输入

4 5
1 2
2 3
3 4
1 3
1 4

输出

1

数据范围

$1≤n,m≤10^5$

点击查看代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int q[N], d[N], n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs()
{
    memset(d, -1, sizeof(d));
    int tt = 0, hh = 0;
    q[0] = 1, d[1] = 0;
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++ tt] = j;
            }
        }
    }
    return d[n];
}

void solve()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs() << endl;
}

signed main()
{
	IOS;
	int _ = 1;
	// cin >> _;
	while(_ --)
		solve();
	return 0;
}

树的重心

例. 树的重心

题目描述

给定一颗树，树中包含 $n$ 个结点（编号 $1∼n$）和 $n−1$ 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式:

第一行包含整数 $n$，表示树的结点数。

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

输出格式:

输出一个整数 $m$，表示将重心删除后，剩余各个连通块中点数的最大值。

输入

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

输出

4

数据范围
$1≤n≤10^5$11

点击查看代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)

using namespace std;

const int N = 1e5 + 10, M = 2 * N;

int h[N], e[M], ne[M], idx;
int n, ans = N;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u)
{
    st[u] = true;
    int res = 0, sum = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n - sum);
    ans = min(res, ans);
    return sum;
}

void solve()
{
    memset(h, -1, sizeof(h));
    cin >> n;
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ans << endl;
}

signed main()
{
	IOS;
	int _ = 1;
	// cin >> _;
	while(_ --)
		solve();
	return 0;
}

最短路

多源汇$Floyd$

时间复杂度：$O(n^3)$

Floyd

void floyd()
{
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                p[i][j] = min(p[i][j], p[i][k] + p[k][j]);
}

单源朴素$Dijkstra$

时间复杂度：$O(nm)$

朴素Dijkstra

void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j]&&(t == -1||dist[j] < dist[t]))
                t = j;
        st[t] = 1;
        for(int j = h[t]; j != -1; j = ne[j])
        {
            int i = e[j];
            dist[i] = min(dist[i], dist[t] + w[j]);
        }
    }
}

单源堆优化$Dijkstra$

时间复杂度：$O(mlog(n))$

堆优化Dijkstra

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pii, vector<pii>, greater<pii> > heap;
    dist[1] = 0;
    heap.push({0, 1});
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int y = t.second;
        if(st[y]) continue;
        st[y] = true;
        for(int i = h[y]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[y] + w[i])
            {
                dist[j] = dist[y] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

单源$Spfa$

时间复杂度：$O(nm)$

Spfa

int spfa()
{
    memset(dist, 0x3f, sizeof(dist));
    queue<int> q;
    dist[1] = 0; st[1] = true;
    q.push(1);
    while(q.size())
    {
        int 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])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}

最小生成树

$Prim$

时间复杂度：$O(nm)$

Prim

const int N = 510, inf = 0x3f3f3f3f;

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

int prim()
{
    memset(dist, inf, 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;
}

Kruskal

时间复杂度：$O(nlogm)$

Kruskal

const int N = 1e5 + 10, inf = 0x3f3f3f3f;

struct node
{
	int a, b, w;
}s[N * 2];

int fa[N], n, m;

int cmp(node a, node b)
{
	return a.w < b.w;
}

void init()
{
	for(int i = 1; i <= n; i ++)
		fa[i] = i;
}

int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int kruskal()
{
	sort(s + 1,s + m + 1, cmp);
	int res = 0, cnt = 0;
	for(int i = 1; i <= m; i ++)
	{
		int a = s[i].a, b = s[i].b, w = s[i].w;
		if(find(a) != find(b))
		{
			fa[find(a)] = find(b);
			cnt ++;
			res += w;
		}
	}
	if(cnt == n - 1) return res;
	return inf;
}

二分图

染色法判断二分图

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)

using namespace std;

const int N = 1e5 + 10, M = 2 * N;

int e[M], ne[M], h[N], color[N], idx;
int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u, int c)
{
    color[u] = c;
    for(int i = h[u]; ~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;
}

void solve()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bool flag = true;
    for(int i = 1; i <= n; i ++)
    {
        if(!color[i])
        {
            if(!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
}

signed main()
{
	IOS;
	int _ = 1;
	// cin >> _;
	while(_ --)
		solve();
	return 0;
}

匈牙利算法求最大匹配数

匹配：在图论中，一个「匹配」是一个边的集合，其中任意两条边都没有公共顶点。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（$agumenting\ path$）。

匈牙利算法模板

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)

using namespace std;

const int N = 410, M = 1e5 + 10;

int h[N], e[M], ne[M], idx;
int a[N], b[N];
int n, m, q, ans;
bool st[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool find(int x)
{
	for(int i = h[x]; ~i; i = ne[i])
	{
		int j = e[i];
		if(!st[j])
		{
			st[j] = true;
			if(!b[j]||find(b[j]))
			{
				b[j] = x;
				return true;
			}
		}
	}
	return false;
}

void solve()
{
	memset(h,  -1, sizeof h);
	cin >> n >> m >> q;
	for(int i = 1; i <= q; i ++)
	{
		int a, b, c;
		cin >> a >> b;
		add(a, b);
	}
	for(int i = 1; i <= n; i ++)
	{
		memset(st, false, sizeof st);
		if(find(i)) ans ++;
	}
	cout << ans << "\n";
}

signed main()
{
	IOS;
	int _ = 1;
	// cin >> _;
	while(_ --)
		solve();
	return 0;
}

拓扑排序

拓扑排序模板

const int N = 100010;

int h[N], e[N], ne[N], idx;
int  n, m, q[N], d[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

bool topsort()
{
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++)
        if(!d[i])
            q[++ tt] = i;
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i =ne[i])
        {
            int j = e[i];
            d[j] --;
            if(d[j] == 0)
                q[++ tt] = j;
        }
    }
    return tt == n - 1;
}

JZTXT

图论

\(DFS\)

例1. 全排列

例2. 八皇后

\(BFS\)

树上问题

树的直径

最近公共祖先LCA

例. 距离

树链剖分

树的层次

树的重心

例. 树的重心

最短路

多源汇\(Floyd\)

单源朴素\(Dijkstra\)

单源堆优化\(Dijkstra\)

单源\(Spfa\)

最小生成树

\(Prim\)

Kruskal

二分图

染色法判断二分图

匈牙利算法求最大匹配数

拓扑排序