DFS求图上联通块
大致思路
图上联通块的求法很多，但是最常见的还是深度优先搜索的求法。
由于是暴力，所以就不过多陈述了，直接写思路：
1
2
3
4
5
6
1）遍历
2）建立一个数组，记录遍历过的点
3）结束条件：所有的点均完成遍历
数据结构：
邻接表：STL_vector
数组：vis[]————存储某点是否来过
代码实现
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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e5 + 100;
int n, m;
vector<int> g[N];
bool vis[N];
void dfs(int u) {
vis[u] = true;
for(int i=0; i<g[u].size(); i++) {
int v = g[u][i];
if(!vis[v]) {
dfs(v);
}
}
}
int main() {
cin >> n >> m;
for(int i=1, u, v; i<=m; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int ans = 0;
memset(vis, false, sizeof(vis));
for(int i=1; i<=n; i++) {
if(!vis[i]) {
dfs(i);
ans ++;
}
}
cout << ans;
return 0;
}
Floyd最短路径算法
Floyd其本质为动态规划以及搜索，算法的思想是，如果我要求出从点i到点j之间的最短路径的距离，如果不能直接到达的话，我可以从中间选择出一个中转点k，先求出从点i到点k的最短距离dis[i][k]，以及点k到点j的最短距离dis[k][j]，如果dis[i][k]+dis[k][j]<dis[i][j]，则我们可以更新dis[i][j]为dis[i][k]+dis[k][j]。
核心代码：
1
2
3
4
5
6
7
for(int k=1; k<=n; k++) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
这里k这重循环枚举的是中转点。必须放在最外层。 具体为什么是这样，自己想一想
Floyd推荐习题：P1119 灾后重建 UVA247 电话圈
