顶点间的简单路径

输入格式
第一行包含三个整数 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
输出

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 

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m, k;
bool st[N];
vector<int> path;

struct Node
{
    int id; // 编号
    Node* next;
    Node(int _id) : id(_id), next(NULL){}
} *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 t)
{
    if(s == t)
    {
        for(auto x : path) 
        cout<<x<<' ';
        cout<<endl;
        return;
    }

    for(auto p = head[s]; p; p = p->next)
    {
        int j = p->id;
        if(!st[j])
        {
            st[j] = true;
            path.push_back(j);
            dfs(j,t);
            path.pop_back();
            st[j] = false;
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    while(k--)
    {
        int s,t;
        scanf("%d%d",&s,&t);
        printf("\n%d -> %d 的所有简单路径：\n",s,t);
        path.push_back(s);
        st[s] = true;
        dfs(s,t);
        st[t] = false;    
        path.pop_back();
    }
    return 0;
}

邻接表，判定顶点间是否存在路径

基于dfs

//dfs 邻接表判定两顶点间路径是否存在
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 510;

int n,m;
bool st[N];

struct Node{
    int id;
    Node * next;
    Node (int _id): id(_id),next(NULL){};
}*head[N];

void add(int a,int b)
{
    auto p = new Node (b);
    p->next = head[a];
    head[a] = p;
}

int s = 1, t = 2;

void dfs(int u)
{
    st[u] = true;
    if(u == t)
    {
        printf("存在%d->%d的路径",s,t);
        return;
    }

    for(auto p = head[u]; p; p = p->next)
        {
            int j = p->id;
            if(!st[j]) dfs(j);
        }
}

int main()
{
    scanf("%d%d",&n,&m);

    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    dfs(s);
    return 0;
}

基于bfs

//bfs 邻接表判定两顶点间路径是否存在
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 510;

int n,m;
bool st[N];

struct Node{
    int id;
    Node * next;
    Node (int _id): id(_id),next(NULL){};
}*head[N];

void add(int a,int b)
{
    auto p = new Node (b);
    p->next = head[a];
    head[a] = p;
}

int ss = 1, tt = 2;

void bfs(int u)
{
    queue <int> q;
    q.push(u);
    st[u] = true;

    while(q.size())
    {
        int t = q.front();
        q.pop();

        if(t == tt)
        {
            printf("\n 存在%d 到 %d的路径",ss,tt);
            return;
        }

        for(auto p = head[t]; p; p = p->next)
        {
            int j = p->id;
            if(!st[j])
            {
                st[j] = true;    
                q.push(j);
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);

    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    bfs(ss);
    return 0;
}

（cr:动力春风）