两点路径问题

想法来源

在周四晚上pta竞选赛时写了一道题目，题目给出了一个无向图，没有闭环，给出了两个点a, b, 要求求出a到b之间有多少种路径，输出路径的数量，在考试的时候我直接跳过了，因为当时时间紧任务重没思路跳过了，考完试后便开始思考这道题怎么写，可以计算出所有路径的同时还可以把路径给输出出来，于是乎，便有了这么一个学习笔记(逼真)！

下面我们来模拟来一道题目

模拟题目

给定一个无向图，不存在重根和闭环，给出两个点n, m，要求求出从n点开始到m点有多少种走法，请输出所有的走法和走法的数量

输入格式

第一行输入两个值n和m，分别表示点的数量和路径数

第2行到第n + 1行，输入两个点a , b，表示a点和b点之间有一条双向路径

最后一行输入两个点op和ed，表示询问op到ed有多少条路可走

输出格式

输出所有可行的路径，隔行输出走法的数量

数据范围

1 <= n, m <= 10^3

样例输入：

样例输出：

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

题解(算法分析)

由于题目要求我们把所有的路径给输出出来，所以我们可以运用深度优先搜索进行暴搜，对于路径的存储，我们可以使用一个二维数组，或者可以写一个邻接矩阵来写，两种都行，下面给出的是邻接矩阵的写法，这样即使n和m的数据范围开到10^5也是可以存储的，只是dfs不一定可以跑那么快

我们可以开一个数组来存储可能的情况

邻接矩阵写法：

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

dfs写法：

void dfs(int x) {
    //如果x是ed的话就说明找到一组解了
    if(x == ed) {
        //把记忆数组输出
        for(int i = 0;i < res;i++) {
            cout << dist[i] << ' ';
        }
        cout << ed << endl;
        return;
    }
    //x搜过了，判断为true
    st[x] = true;
    //把x加入记忆数组中
    dist[res++] = x;
    //遍历x与哪些点相交
    for(int i = h[x];i != -1;i = ne[i]) {
        int j = e[i];
        //如果这个点没有被遍历过
        if(!st[j]) {
            //对这个点进行dfs
            dfs(j);
        }
    }
    //还原现场
    st[x] = false;
    res--;
}

全代码 —- 纯净版

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
typedef long long ll;
int dist[N];
int n, m, res, sum;
int op, ed;
int ne[N], e[N], idx, h[N];
bool st[N];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int x) {
    if(x == ed) {
        for(int i = 0;i < res;i++) {
            cout << dist[i] << ' ';
        }
        cout << ed << endl;
        sum++;
        return;
    }
    st[x] = true;
    dist[res++] = x;
    for(int i = h[x];i != -1;i = ne[i]) {
        int j = e[i];
        if(!st[j]) {
            dfs(j);
        }
    }
    st[x] = false;
    res--;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i = 1;i <= m;i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    cin >> op >> ed;
    dfs(op);
    cout << sum << endl;
    return 0;
}