23.03.30 学习
留坑
链式前向星真是个好玩意,以前懵懵懂懂的终于图论题碰多了慢慢明白,就得一点点手动去模拟
目前的思路
for()
:遍历是用来决定该节点的分叉走向,当一个节点有多条出边时,多叉走路dfs()
:是用来在图之间进行从上个点走到下个点的,单链式走路
整体很像全排列,dfs用于位数移动,for用于每一位的取值遍历
参考题解:https://www.acwing.com/blog/content/2416/
图解和详细的路径展示,看题解,在这里不再赘述
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
// for (int i = h[a]; i != -1; i = ne[i]) {
// cout << i << ' ' << e[i] << ' ' << ne[i] << ' ' << idx << ' ' << h[a];
// cout << endl;
// }
}
int cnt = 0;
void dfs(int u) {
st[u] = true;
//cout << u << endl; // u就是图中的每一个点
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
cout << u << "->" << j << endl; // 这里可以使用二维vector以数组形式存错所有的边
if (!st[j]) {
cnt ++ ; // cnt是递归了多少次,也就是idx在图中走了多少条边,应该是等于m的,证明所有点都遍历到了
dfs(j);
}
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
int start;
for (int i = 0; i < m; i ++ ) {
int a, b, c;
cin >> a >> b;
add(a, b);
if (i == 0) start = a;
}
dfs(1);
//cout << cnt;
return 0;
}