图论入门题解

P5318 【深基18.例3】查找文献 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

用vectorgraph[N]存图 类似于defaultdict(list)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
vector<int>graph[N];
int n, m;
bool vis[N];

void dfs(int x)
{
	vis[x] = true;
	cout << x << " ";
	for (int i = 0; i < graph[x].size(); i++)
	{
		if (!vis[graph[x][i]])
		{
			dfs(graph[x][i]);
		}
	}
}

void bfs(int x)
{
	queue<int>q;
	q.push(x);
	vis[x] = 1;
	while (!q.empty())
	{
		int a = q.front();
		q.pop();
		cout << a << " ";
		for (int i = 0; i < graph[a].size();i++)
		{
			if (!vis[graph[a][i]])
			{
				vis[graph[a][i]] = true;
				q.push(graph[a][i]);
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].emplace_back(b);
	}
	for (int i = 1; i <= n; i++)
		sort(graph[i].begin(), graph[i].end());

	dfs(1);
	cout << endl;

	memset(vis, false, sizeof vis);

	bfs(1);
	cout << endl;
	return 0;
}

P3916 图的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

有向图求每个点能到达的编号最大的点

图论的经典做法 存反图然后从最大的点开始遍历他能到达的所有点 更新 后续如果这个点已经更新过了 就不再更新了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
using namespace std;
const int N = 100010;
vector<int>fgraph[N];
int dis[N] = { 0 };

void dfs(int x, int d)
{
	if (dis[x] != 0)
		return;
	dis[x] = d;
	for (int i = 0; i < fgraph[x].size(); i++)
	{
		dfs(fgraph[x][i], d);
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	while (m--)
	{
		int u, v;
		cin >> u >> v;
		fgraph[v].push_back(u);
	}
	for (int i = n; i >= 0; i--)
	{
		dfs(i, i);
	}
	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << " ";
	}
}

P1113 杂务 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

经典拓扑+动态规划

把前面的杂物干完才能干后面的事 拓扑排序

并且加上了动态规划（有点类似dijkstra） 完成所有杂物的最短时间 每次循环更新 到u这个任务需要的最短时间 （即f[u] = max(f[u], f[x] + t[u]）到u的最短 即到源点到x的最短加上到x到u的最短

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
const int N = 500500;

vector<int>graph[N];
int deg[N];
int f[N];
int t[N];
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int u, v;
		cin >> u >> t[i];
		while (cin >> v && v)
		{
			graph[v].push_back(u);
			deg[u]++;
		}
	}
	queue<int>q;
	for (int i = 1; i <= n; i++)
	{
		if (deg[i] == 0)
		{
			q.push(i);
			f[i] = t[i];
		}
	}
	while (!q.empty())
	{
		int x = q.front();
		q.pop();

		for (int i = 0; i < graph[x].size(); i++)
		{
			int u = graph[x][i];
			deg[u]--;
			if (deg[u] == 0)
			{
				q.push(u);
			}
			f[u] = max(f[u], f[x] + t[u]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans = max(ans, f[i]);
	}
	cout << ans << endl;
}

P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

求食物链的数量（食物链必须到最高消费者 即不被捕食的动物 即出度为0的）

拓扑排序+动态规划

比如a->b->c 每次更新时 nums[b] = nums[b] + nums[a] 把到第a的食物链条数全部累加到b中 最后把出度为0的点的条数加上 即为答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
const int mod = 80112002;
vector<int>graph[N];
int deg[N], out[N], nums[N];
int main()
{
	int n, m;
	cin >> n >> m;
	int a, b;

	while (m--)
	{
		cin >> a >> b;
		graph[a].push_back(b);
		deg[b]++;
		out[a]++;
	}
	queue<int>q;

	for (int i = 1; i <= n; i++)
	{
		if (deg[i] == 0)
		{
			q.push(i);
			nums[i] = 1;
		}
	}

	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < graph[x].size(); i++)
		{
			int u = graph[x][i];
			deg[u]--;
			if (deg[u] == 0)
			{
				q.push(u);
			}
			nums[u] = (nums[u] + nums[x]) % mod;
		}

	}
	long long ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (out[i] == 0)
		{
			ans = (nums[i] + ans)%mod;
		}
	}
	cout << ans;
}

P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

最长路问题 还是动态规划 d[i] = max(d[x] + mp[x ] [ i ], d[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const int N = 2000, M = 55000;
int n, m;
int d[N], mp[N][N];

int main()
{
	memset(d, -1, sizeof d); 
	d[1] = 0;
	cin >> n >> m;
	int u, v, w;
	while (m--)
	{
		cin >> u >> v >> w;
		mp[u][v] = max(mp[u][v], w);
	}

	queue<int>q;
	q.push(1);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 1; i <= n; i++)
		{
			if (mp[x][i] && d[i] < d[x] + mp[x][i])
			{
				d[i] = d[x] + mp[x][i];
				q.push(i);
			}

		}
	}

	cout << d[n] << endl;

}

[P2853 USACO06DEC] Cow Picnic S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

求有几个地方 是所有的奶牛都可以的到达的

那每次走过的时候次数+1 当all[x] == k 的时候就代表这个点都可以到达

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, k;
int a[N], vis[N], all[N];
vector<int>graph[N];

void dfs(int x)
{
	if (vis[x] != 0)
		return;
	vis[x] = 1;
	all[x] += 1;
	for (int i = 0; i < graph[x].size(); i++)
	{
		int y = graph[x][i];
		if (vis[y] == 0)
			dfs(y);
	}
}

int main()
{
	cin >> k >> n >> m;
	for (int i = 1; i <= k; i++)
		cin >> a[i];
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
	}
	for (int i = 1; i <= k; i++)
	{
		dfs(a[i]);
		memset(vis, 0, sizeof vis);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (all[i] == k)
			ans += 1;
	}
	cout << ans;
}

P1363 幻象迷宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

无线的地图 那么只要它能够回到原点 就说明可以从一个点到另一个点 就可以无限走 就符合题意

用vis储存横纵坐标和是否访问

每次进入先判断该点（是取模过的点 ***）是否已经访问过 如果访问过 并且x， y跟之前的不一样（只要有一个不一样就行）那就说明走到了另一个地图的原点 说明可以无限

如果访问过 并且是回到了原点 那就退回

标记该点为已访问 像四个方向拓展 lx和ly用来记录是否走出 要取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int m, n, sx, sy, dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 }, ans = 0;
const int N = 1510;
bool graph[N][N] = { false };
int vis[N][N][3] = { 0 };
void dfs(int x, int y, int lx, int ly)
{
	if (vis[lx][ly][2] && (vis[lx][ly][0] != x || vis[lx][ly][1] != y))
	{
		ans = 1;
		return;
	}

	if (vis[lx][ly][2] && vis[lx][ly][0] == x && vis[lx][ly][1] == y)return;
	vis[lx][ly][0] = x; vis[lx][ly][1] = y; vis[lx][ly][2] = 1;
	int nx, ny;
	for (int w = 0; w < 4; w++)
	{
		nx = (lx + dx[w] + n) % n;
		ny = (ly + dy[w] + m) % m;
		if (graph[nx][ny])dfs(x + dx[w], y + dy[w], nx, ny);
	}
	
}
int main()
{
	char c;
	while (cin >> n >> m)
	{
		memset(vis, false, sizeof(vis));
		memset(graph, false, sizeof(graph));
		ans = 0;

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cin >> c;
				if (c == '.')graph[i][j] = true;
				else if (c == 'S')
				{
					sx = i, sy = j;
					graph[i][j] = true;
				}
				else graph[i][j] = false;
			} 
		}
		dfs(sx, sy, sx, sy);
		if (ans)puts("Yes");
		else puts("No");
	}
}

[省份数量](547. 省份数量 - 力扣（LeetCode）)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# dfs 用一个标记数组记下已经访问过的城市 然后遍历所有的城市 每一次dfs都可以遍历一个省份的所有城市
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
		cities = len(isConnected)
        province = 0
        vis = [0] * cities

        def dfs(i):
            for j in range(cities):
                if not vis[j] and isConnected[i][j] == 1:
                    vis[j] = 1
                    dfs(j)

        for i in range(cities):
            if not vis[i]:
                vis[i] = 1
                province += 1
                dfs(i)

        return province
    
   # 也可用并查集 对每个点查找祖先结点 合并 最后有几个祖先结点就有几个省份 
# 重点在并查集的写法
		uf = UnionFind()
        for i in range(len(isConnected)):
            uf.add(i)
            for j in range(i):
                if isConnected[i][j] == 1:
                    uf.merge(i,j)
        return uf.num_of_sets

class UnionFind:
    def __init__(self):
        self.father = {}
        self.num_of_sets = 0

    def find(self,x):
        root = x
        while self.father[root] != None:
            root = self.father[root]
		# 让并查集更宽 减少时间复杂度
        while x != root:
            original_father = self.father[x]
            self.father[x] = root
            x = original_father
        return root

    def merge(self,x,y):
        root_x, root_y = self.find(x),self.find(y)

        if root_x != root_y:
            self.father[root_x] = root_y
            self.num_of_sets -= 1

    def add(self,x):
        if x not in self.father:
            self.father[x] = None
            self.num_of_sets += 1

[找到最终的安全状态](802. 找到最终的安全状态 - 力扣（LeetCode）)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
"""
所有结点都通向终端结点的结点为安全结点，只要没有环的话，那所有结点肯定都是通向终端结点的，所以题目就是求出所有不组成环的结点
"""

"""
dfs 深搜找环 用三色标记法，未访问为0，还处于递归栈中或在环上为1，搜素完毕是安全结点为2
一开始全为0，开始搜索，搜到的0标记为1，当搜索到的是1，说明遇到环了，此时退出。当没有搜到环 在退出dfs前，将标记改为2，表示安全
""" 
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
        color = [0] * n
        
        def safe(x: int)->bool:
            # 访问已经搜过的结点 1为有环 2为无环
            if color[x] > 0:
                return color[x] == 2
            # 如果是0
            color[x] = 1
            for y in graph[x]:
                # 快速退出
                if not safe(y):
                    return False
            # 如果上面检测了都没有环 那么就说明该结点无环 标记为2并返回True
            color[x] = 2
            return True
       	
        return [i for i in range(n) if safe(i)]
    
    
    """
    拓扑排序 拓扑排序可以用来判环，如果一个结点没有出边那么就是安全的（终端）如果一个结点的出边连接的结点是安全的，那该结点也是安全的
    那么可以把图的所有边反向，得到一个反图，再在反图上拓扑排序
    循环结束后 所有入度为0的结点都是安全的
    意思是，原图的出度为0的结点，和指向出度为0的结点的结点
    （由于存了反图并拓扑排序
    """
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		rg = [[] for _ in graph]
        # 如 graph[0] = [1,2] 0指向1 2反向：  x = 0 ys = [1,2] 让1指向0 2 指向0
        for  x, ys in enumerate(graph):
			for y in ys:
				rg[y].append(x)
        # in_deg 表示入度 值为graph的每个数组的长度（即每个点的出度）（就是反图的入度）
        in_deg = [len(ys) for ys in graph]
        
        q = deque([i for i, d in enumerate(in_deg) if d == 0])
		while q:
            for x in rg[q.popleft()]:
                in_deg[x] -= 1
                if in_deg[x] == 0:
                    q.append(x)
        return [i for i, d  in enumerate(in_deg) if d == 0]

颜色交替的最短路径 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 其实就是双源bfs（边权为1 可以直接用单源的算法 初始化加上另一个源点） 并且每次只能交替走颜色不同的路 用邻接矩阵来储存图 储存点是否访问等 用点对 第二个参数表示颜色
class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        g = [[] for _ in range(n)]
        for x, y in redEdges:
            g[x].append((y,0))
        for x, y in blueEdges:
            g[x].append((y,1))
        

        dis = [-1] * n
        vis = {(0,0),(0,1)}
        q = {(0,0),(0,1)}
        level = 0
        while q:
            tmp = q
            q = []
            for x, color in tmp:
                if dis[x] == -1:
                    dis[x] = level
                for p in g[x]:
                    if p[1] != color and p not in vis:
                        vis.add(p)
                        q.append(p)
            level += 1
        return dis

通知所有员工所需的时间 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        g = collections.defaultdict(list)
        for i in range(n):
            g[manager[i]].append(i)

        q = collections.deque()
        q.append((headID, 0))
        res = 0
        while q:
            tid, val = q.popleft()
            if len(g[tid]) == 0:
                res = max(res, val)
            else:
                for ne in g[tid]:
                    q.append((ne, val + informTime[tid]))
        return res

1466. 重新规划路线 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 这个题要找 到0的路线 先用defaultdict建图 正向记为1反向记为0 然后bfs 
class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        res = 0
        g = defaultdict(list)
        for a, b in connections:
            g[a].append((b, 1))
            g[b].append((a, 0))
        
        q = deque([0])
        vis = [False] * n
        while q:
            cur = q.popleft()
            # 遍历所有和cur相邻的边
            for end, dirction in range(g[cur]):
                if not vis[end]:
                    vis[end] = True
                    # 如果方向不对就反转
                    res += dirction
                    q.append(end)
        return res
    
    
# 或者 用set一次遍历  有点问题
class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        s = {0}
        res = 0
        for l, r in connection:
            if r in s:
                s.add(l)
            # 右边不通向0 并且左边通向0 （左边通向右边） 那就让r->l r就可以到0
            elif l in s:
                s.add(r)
                res += 1
        return res

1192. 查找集群内的关键连接 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 用Tarjan算法 标记图中的所有环 然后把所有环和环外链接线加入答案 因为环内肯定不存在关键路径 只有在环与非环的链接处 或者所有的非环之间 才有关键路径
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)
        for con in connections:
            graph[con[0]].append(con[1])
            graph[con[1]].append(con[0])

        
        idx = [-1] * n
        res = []

        def dfs(curnode, curid, parent):
            idx[curnode] = curid

            for nextnode in graph[curnode]:
                if nextnode == parent:
                    continue
                elif idx[nextnode] == -1:
                    idx[curnode] = min(dfs(nextnode,curid + 1, curnode),idx[curnode])
                else:
                    idx[curnode] = min(idx[curnode],idx[nextnode])

            # 说明存在环 （此时的curnode为入口结点）
            if idx[curnode] == curid and curnode != 0:
                res.append((parent, curnode))
            # 记得返回idx
            return idx[curnode]
        

        dfs(0,0,-1)
        return res

934. 最短的桥 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 两座相同的岛 先找到第一个不为0的数然后dfs标记这个岛的全部，然后用bfs搜索当第一次搜到第二个岛的step即是答案，注意dfs的时候要把第一个岛全部放入q（因为每个点都可能是距离第二个岛最近的点）搜完上下左右一圈后step + 1 （不需要vis数组记录 直接把走过的设为-1即可）
class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        def dfs(x, y):
            grid[x][y] = -1
            q.append((x, y))
            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                    dfs(nx, ny)

        n = len(grid)
        q = deque()
        i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j])
        dfs(i, j)
        step = 0

        while True:
            for _ in range(len(q)):
                x, y = q.popleft()
                for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):
                    if 0 <= nx < n and 0 <= ny < n :
                        if grid[nx][ny] == 1:
                            return step
                        if grid[nx][ny] == 0:
                            grid[nx][ny] = -1
                            q.append((nx, ny))
            step += 1

127. 单词接龙 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 每次枚举26个字母 一一替换单词 直到找到wordList的单词 如果是end的话就直接返回 否则step+1放入q继续bfs
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if beginWord == endWord:
            return 0
        wordList = set(wordList)
        if endWord not in wordList:
            return 0
        
        word = [chr(i) for i in range(97, 123)]
        q = deque([(beginWord, 1)])
        while q:
            cur, step = q.popleft()
            for i, x in enumerate(cur):
                for y in word:
                    if x != y:
                        nxt = cur[:i] + y + cur[i + 1:]
                        if nxt in wordList:
                            if nxt == endWord:
                                return step + 1
                            q.append((nxt, step + 1))
                            wordList.remove(nxt)
        return 0

126. 单词接龙 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 这个方法相当于是每次把step=1的所有数都找出来并且加进去 把所有step=2的都找出来加进去这样（"hit","hot","dot" and "hit","hot","lot"）     当q（内层）取完之后表示当前步数可以链接的下一个单词已经全部找到 可以step+1 然后把s中暂存的给q 再次循环    直到end 加入答案 （当内层q为0的时候表示所有路径都已经加进去 就直接return） 当q（外层）取完（也就是sq交换的时候s为[]）之后表示所有路径都已经走过 但是还没有遇到end 这时返回[]
# 首先 建图方面 建立这个单词可以变的其他单词 变化处用* 表示 用defaultdict后面可以快速访问 
# 然后q用来存储当前值和当前路径 s与q相同 但是s是用来存储每轮的数据 每次开始时s都为[] （保证数据 相当于temp）
class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordList = set(wordList)
        if endWord not in wordList:
            return []
        dic = defaultdict(list)
        n = len(beginWord)
        for w in wordList:
            for i in range(n):
                dic[w[:i] + '*' + w[i + 1:]].append(w)
        
        q, s = [(beginWord, [beginWord])], []
        res = []
        vis = set()
        while q:
            while q:
                w, path = q.pop()
                vis.add(w)
                if w == endWord:
                    res.append(path)
                for i in range(n):
                    for nxt in dic[w[:i] + '*' + w[i + 1:]]:
                        if nxt not in vis:
                            s.append((nxt, path + [nxt]))
            if res:
                return res
            q, s = s, q
        return []

542. 01 矩阵 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 多起点的最短路问题 可以将所有的0 看成同一个源点 然后使用bfs 因为每次扩散一轮 所有的都加一时候再扩散下一轮（队列 先进先出）每次只需要搜索四个方向 然后再原来的ret的基础上加一
class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        n, m = len(mat), len(mat[0])
        ret = [[-1] * m for _ in range(n)]
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        q = deque()
        for i in range(n):
            for j in range(m):
                if mat[i][j] == 0:
                    ret[i][j] = 0
                    q.append([i,j])
        
        while q:
            i, j = q.popleft()
            for k in range(4):
                ni, nj = i + dx[k], j + dy[k]
                if 0 <= ni < n and 0 <= nj < m and ret[ni][nj] == -1:
                    ret[ni][nj] = ret[i][j] + 1
                    q.append([ni, nj])

        return ret

863. 二叉树中所有距离为 K 的结点 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        # 首先用字典node_parent存储每个结点的父节点
        node_parent = dict()

        def dfs_find_parent(node: TreeNode) -> None:
            if node is None:
                return 
            if node.left:
                node_parent[node.left] = node
            if node.right:
                node_parent[node.right] = node
            dfs_find_parent(node.left)
            dfs_find_parent(node.right)


        dfs_find_parent(root)
        if k == 0:
            return [target.val]
        res = []

        q = deque()
        vis = set()
        q.append(target)
        vis.add(target)
        # 现在依次遍历和target距离为level的结点（波纹法 一层层搜索）
        level = 0
        while q and level < k:
            level += 1 # 先加还是后加取决于level初值
            for _ in range(len(q)):
                x = q.popleft()
                for y in [node_parent[x] if x in node_parent else None, x.left, x.right]: # 遍历和当前点相邻的所有结点（每次搜索一层 注意要用set判重）
                    if y and y not in vis:
                        if level == k:
                            res.append(y.val)
                        q.append(y)
                        vis.add(y)
        return res

864. 获取所有钥匙的最短路径 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 不同之处在于 并不是一个点只能走一次 而是可以多次走 找到最短的路
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        n = len(grid)
        m = len(grid[0])
        cnt = 0
        # dis 用于记录每个点走的距离 不同的是 现在有3个状态 多了一个钥匙数的状态 
        dis = defaultdict(lambda: 0x3f3f3f3f)
        
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '@':
                    q = deque([(i, j, 0)])
                    dis[(i, j, 0)] = 0
                elif grid[i][j].islower():
                    cnt += 1


        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        
        
        while q:
            i, j, cur = q.popleft()
            step = dis[(i,  j, cur)]
            for k in range(4):
                ni, nj = i + dx[k], j + dy[k]
                if 0 <= ni < n and 0 <= nj < m:
                    c = grid[ni][nj]
                    if c == '#':
                        continue
                    # 先将cur右移c位然后&1判断是否为1
                    if 'A' <= c <= 'Z' and (cur >> (ord(c) - ord('A')) & 1) == 0:
                        continue
                    ncur = cur
                    if 'a' <= c <= 'z':
                        # 标记为已有
                        ncur |= (1 << ord(c) - ord('a'))
                    if ncur == (1 << cnt) - 1:
                        return step + 1
                    # 如果曾经走到过这里 并且步数更少的话 更新 （如果没有走到过的话 那就是0x3f3f3f3f 必定更新）
                    if step + 1 < dis[(ni, nj, ncur)]:
                        dis[(ni, nj, ncur)] = step + 1
                        q.append((ni, nj, ncur))
        
        return -1

1334. 阈值距离内邻居最少的城市 - 力扣（LeetCode）

题目要求一个城市在距离小于distanceThreshold下能够到达的城市

可以直接求 对每个城市进行搜索 也可以直接用Floyd 算法求出每两个城市之间的距离 再找距离小于dis的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[inf] * n for _ in range(n)]
        for a, b, w in edges:
            graph[a][b] = graph[b][a] = w
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        
        ans = min_cnt = 0
        for i in range(n):
            cnt = 0
            for j in range(n):
                if j != i and graph[i][j] <= distanceThreshold:
                    cnt += 1
            if cnt <= min_cnt:
                min_cnt = cnt
                ans = i
        return ans

2646. 最小化旅行的价格总和 - 力扣（LeetCode）

树形DP 要算所有的路径 的总和可以先暴力DFS算出所有的路径的贡献：也就是比如0-1-2中求(0,2)(1,2) 那么1-2 算了两次 这样求出所有边走的次数cnt[x]

遍历(start, end) 求cnt

然后知道每个边的 次数之后再用树形DP（打家劫舍3）求出最小值 每个点减或不减

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        cnt = [0] * n
        for start, end in trips:
            def dfs(x:int, fa:int) -> bool:
                if x == end:
                    cnt[x] += 1
                    return True
                for y in g[x]:
                    # dfs(y) 是为了说明这是可以到end的路(到end之后再往回更新cnt)
                    if y != fa and dfs(y):
                        cnt[x] += 1
                        return True
                return False
        	dfs(start, -1)
        
       	# 现在就得到了走的边的次数 再加上已知点的权值 用树形DP求
        def dfs(x:int, fa:int) -> (int, int):
            now_not_halve = price[x] * cnt[x]
            now_halve = price[x] * cnt[x] // 2
            for y in g[x]:
                if y != fa:
                    kid_not_halve, kid_halve = dfs(y, x)
                    now_not_halve += min(kid_not_halve, kid_halve)
                    now_halve += kid_not_halve
            return now_not_halve, now_halve
        return min(dfs(0, -1))

1631. 最小体力消耗路径 - 力扣（LeetCode）

看起来像DP但是其实是图论的题 为什么呢 因为dp只能向一个方向更新 比如只能一直向下 选择 [i + 1] [j - 1] 、[i + 1] [j] 、[i + 1] [j + 1] 这三种 但是这个题明显就是有4个方向 类似BFS

方法一、 二分+BFS

二分可能的最大差异值 用bfs计算 如果最大差异大于x则…

注意这里维护的是最大差异 每次当更新的时候如果差异值小于x才更新 最终如果能到达右下角说明这个x可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        n, m = len(heights), len(heights[0])
        l, r = 0, 10**6+10
        def bfs(mid):
            dx = [0, 1, 0, -1]
            dy = [1, 0, -1, 0]
            q = deque()
            q.append((0, 0))
            minn = maxn = heights[0][0]
            vis = [[False] * m for i in range(n)]
            vis[0][0] = 1
            while q:
                x, y = q.popleft()

                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny] and abs(heights[x][y] - heights[nx][ny]) <= mid:
                        vis[nx][ny] = 1
                        q.append((nx, ny))

            return vis[n - 1][m - 1]

方法二、并查集

其实是Kruskal算法 对所有边排序之后 不断添加边 同时维护最大差异值 直到左上角和右下角联通 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        n, m = len(heights), len(heights[0])
        def find(x):
            if fa[x] == x:
                return x
            fa[x] = find(fa[x])
            return fa[x]
        def union(x, y):
            fa[find(x)] = find(y)

        edgelen = []
        fa = [i for i in range(n * m)]
        for i in range(n):
            for j in range(m):
                pos = i * m + j
                if i < n - 1:
                    edgelen.append([abs(heights[i + 1][j] - heights[i][j]), pos, pos + m])
                if j < m - 1:
                    edgelen.append([abs(heights[i][j + 1] - heights[i][j]), pos, pos + 1])
        
        edgelen.sort()
        for e in edgelen:
            union(e[1], e[2])
            if find(0) == find(m * n - 1):
                return e[0]
        return 0

方法三、最短路

Dijikstra算法 只不过本来维护最短距离 现在维护最大差异 本来是存边 现在不需要存边 直接用BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        n, m = len(heights), len(heights[0])
        q = [(0, 0, 0)]
        dis = [inf] * (m * n)
        dis[0] = 0
        vis = set()
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        while q:
            d, x, y = heapq.heappop(q)
            pos = x * m + y
            if pos in vis:
                continue
            if (x, y) == (n - 1, m - 1):
                break
            vis.add(pos)
            
            for i in range(4):
                nx = dx[i] + x
                ny = dy[i] + y
                if 0 <= nx < n and 0 <= ny < m and max(d, abs(heights[x][y] - heights[nx][ny])) <= dis[nx * m + ny]:
                    dis[nx * m + ny] = max(d, abs(heights[x][y] - heights[nx][ny]))
                    heapq.heappush(q, (dis[nx * m + ny], nx, ny))
        return dis[m * n - 1]

1345. 跳跃游戏 IV - 力扣（LeetCode）

BFS 但是要分情况 主要是存图要用map存 map[arr[i]].push_back(i);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int minJumps(vector<int>& arr) 
    {
        unordered_map<int, vector<int>>mp;
        for (int i = 0; i < n; i++)
        {
            mp[arr[i]].push_back(i);
        }
        const int inf = 0x3f3f3f3f;
        queue<int>q;
        vector<int>dist(n, inf);
        q.push(0);
        dist[0] = 0;
        while (!q.empty())
        {
            int x = q.front(), step = dist[x];
            q.pop();
            if (x == n - 1)return step;
            if (x + 1 < n && dist[x + 1] == inf)
            {
                dist[x + 1] = step + 1;
                q.push(x + 1);
            }
            if (x - 1 >= 0 && dist[x - 1] == inf)
            {
                dist[x - 1] = step + 1;
                q.push(x - 1);
            }
            for (auto y : mp[arr[x]])
            {
                if (dist[y] == inf)
                {
                    dist[y] = step + 1;
                    q.push(y);
                }
            }
            mp[arr[x]].clear();
        }
        return -1;
    }
};

1207. 大臣的旅费 - AcWing题库

求树的直径问题

要求相距最远的两个城市 也就是求树的直径

先任取一点x 做dfs 求出离x最远的点y 再对y进行dfs所得到的离y最远的点maxu 这两点的连接就是树的直径

用dis记录任意点到i点的最远距离

dfs中需要添加father 防止回头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n ;
int w[N] , e[N] , ne[N] , h[N] , idx ;
int maxu , maxd ;
int dis[N];
void add(int a , int b , int c )
{
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++ ;
}
void dfs(int u , int fa , int d)
{
    dis[u] = d;
    for(int i = h[u] ; i != -1 ; i = ne[i])
    {
        int j = e[i];
        if(j != fa)
            dfs(j,u,d + w[i]);
    }
}
int main()
{
    cin >> n ;
    memset(h,-1,sizeof h);
    for (int i = 0; i < n; i++)
    {
        int a , b , c ;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1,0);
    for (int i = 1 ; i <= n; i++)
    {
        if (dis[maxu] < dis[i]) 
        {   
            maxu = i;
            maxd = dis[maxu];
        }
    }
    
    dfs(maxu,-1,0);
    for (int i = 1 ; i <= n; i++)
    {
        if (dis[maxu] < dis[i]) 
        {   
            maxu = i;
            maxd = dis[maxu];
        }
    }
    cout << maxd * 10 + (maxd + 1ll) * maxd / 2 << endl ;
    return 0;
}

algorithm
#Ans
图论入门题解
https://brtulien.github.io/2023/08/26/图论入门题解/
作者
Brtulien
发布于
2023年8月26日
更新于
2024年7月1日
许可协议