[Vssue]kamacoder/0098.所有可达路径.md

[youngyangyang04]

https://www.programmercarl.com/kamacoder/0098.%E6%89%80%E6%9C%89%E5%8F%AF%E8%BE%BE%E8%B7%AF%E5%BE%84.html

[yfabc123]

//c语言邻接矩阵和邻接表(底部)写法
#include <ctype.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*邻接矩阵+邻接表写法*/
int N, M;
int* path;
int pathSize;
int count;    //记录路径数
int** res;    //结果集
int* pathLen; //记录每个路径上的节点个数

void dfs(int graph[N + 1][N + 1], int end)
{
    if (end == N)
    {
        pathLen[count] = pathSize;
        res[count] = (int*)malloc(sizeof(int) * pathSize);
        memcpy(res[count++], path, sizeof(int) * pathSize);
        return;
    }
    for (int i = 1; i <= N; i++)
    {
        if (end == i || graph[end][i] == 0)
            continue;
        path[pathSize++] = i;
        dfs(graph, i);
        pathSize--;
    }
}
int main()
{
    scanf("%d %d", &N, &M);
    int graph[N + 1][N + 1];
    memset(graph, 0, sizeof(graph));
    for (int i = 0; i < M; i++) //是M 不是N 注意点
    {
        int start, end;
        scanf("%d %d", &start, &end);
        graph[start][end] = 1;
    }
    res = (int**)malloc(sizeof(int*) * 10000); //假设有10w个方案
    pathLen = (int*)malloc(sizeof(int) * 10000);
    path = (int*)malloc(sizeof(int) * N);
    //先找到 起点为1的点
    path[pathSize++] = 1;
    dfs(graph, 1);
    if (count == 0)
        printf("-1");

    for (int i = 0; i < count; i++)
    {
        for (int j = 0; j < pathLen[i]; j++)
        {
            printf("%d", res[i][j]);
            if (j != pathLen[i] - 1)
                printf(" ");
        }
        printf("\n");
    }

    return 0;
}

/*
//邻接表
#include <ctype.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node
{
    int data;
    struct Node* next;
} Node;

void insert(int val, Node** head) //插入到指定链表末尾
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;
    node->next = NULL;
    if (*head == NULL)
    {
        *head = node;
        return;
    }
    Node* ptr = *head;
    while (ptr->next)
        ptr = ptr->next;

    ptr->next = node;
}

int N, M;
int* path;
int pathSize;
int count;    //记录路径数
int** res;    //结果集
int* pathLen; //记录每个路径上的节点个数

void dfs(Node* graph[N + 1], int end)
{
    if (end == N)
    {
        pathLen[count] = pathSize;
        res[count] = (int*)malloc(sizeof(int) * pathSize);
        memcpy(res[count++], path, sizeof(int) * pathSize);
        return;
    }
    for (Node* ptr = graph[end]; ptr; ptr = ptr->next)
    {
        path[pathSize++] = ptr->data;
        dfs(graph, ptr->data);
        pathSize--;
    }
}

int main()
{
    scanf("%d %d", &N, &M);
    Node* graph[N + 1];
    memset(graph, 0, sizeof(graph));
    for (int i = 0; i < M; i++) //是M 不是N 注意点
    {
        int start, end;
        scanf("%d %d", &start, &end);
        insert(end, &graph[start]);
    }
    res = (int**)malloc(sizeof(int*) * 10000); //假设有10w个方案
    pathLen = (int*)malloc(sizeof(int) * 10000);
    path = (int*)malloc(sizeof(int) * N);
    //先找到 起点为1的点
    path[pathSize++] = 1;
    dfs(graph, 1);
    if (count == 0)
    {
        printf("-1");
        return 0;
    }
    for (int i = 0; i < count; i++)
    {
        for (int j = 0; j < pathLen[i]; j++)
        {
            printf("%d", res[i][j]);
            if (j != pathLen[i] - 1)
                printf(" ");
        }
        printf("\n");
    }

    return 0;
}*/

[chaofengdev]

为什么我觉得代码随想录写的好呢，因为很多碎碎念和我当初学习时心里想的一模一样。

[chaofengdev]

现在回头来看，真的一气呵成。