题目描述

假设图用邻接表表示，设计一个算法，输出从顶点 i 到顶点 j 的所有简单路径

输入格式

第一行包含三个整数 n, m 和 k。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x, y)。
接下来 k 行，每行包含两个整数 s 和 t，表示要求输出顶点 s 到顶点 t 的所有简单路径。

样例

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

思路

传统深搜

C++ 代码

#include<bits/stdc++.h>
using namespace std;
vector<int> path;
const int N = 1e5 + 10;
bool st[N];
int n, m, k;
int a, b;
struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(nullptr) {}
}*head[N];             //注意语法

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];      //头插法
    head[a] = p;
}

void dfs(int s, int e)
{
    st[s] = true;             //配合剪枝
    path.push_back(s);
    if(s == e)
    {
        for(auto x : path) cout << x << ' ';
        cout << endl;
    }
    else
    {
        for(Node* p = head[s]; p; p = p->next)
        {
            int j = p->id;
            if(st[j] == false)        //剪枝
            {
                dfs(j, e);
            }
        }
    }

    st[s] = false;
    path.pop_back();
    return ;
}
int main()
{
    cin >> n >> m >> k;
    while(m--)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }

    while(k--)
    {
        int start, end;
        cin >> start >> end;
        cout << start << "到" << end << "的所有简单路径:" << endl;
        dfs(start, end);
        cout << endl;
    }

    return 0;
}

输出

1到4的所有简单路径:
1 3 4 
1 2 7 4 
1 2 4 

2到5的所有简单路径:
2 7 4 5 
2 4 5 

1到5的所有简单路径:
1 3 4 5 
1 2 7 4 5 
1 2 4 5