Skip to content

11233: 【原1233】Path

题目

题目描述

author: DS TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1233

Description

大家还记得邻接表类吗?(如果你已经不记得,请看书上的P343页开始的内容)没错,邻接表是表示稀疏图(边数比较少的图)的一种很好的数据结构。

现在,我们要求使用深度优先遍历(若对深度优先搜索DFS的内容不清楚,请看P348)的思想,利用邻接表类,对给定的有向图,找出从指定结点start出发,长度为M的所有简单路径(简单路径是顶点序列中顶点不重复出现的路径)的数量。

为简化题目,我们还是约定:用正整数1,2,3……n来表示每个结点的ID(编号)。(输入可能有重边)

Input Format

第1行:n m start M //正整数n ,代表图中结点的数量。非负整数m代表要图中有向边的数量。start为起点编号,M为题中的简单路径长度

第2行到第1+m行: a b //每行两个整数:代表结点a到结点b有一条有向边(a->b),权值为1

Output Format

一个整数k,代表长度为M的所有简单路径的数量

Sample Input1

5 4 1 2
1 2
2 3
3 4
4 5

Sample Output1

1               //从1出发,长度为2的简单路径只有一条:1->2->3

Sample Input2

6 5 1 2
1 2
2 3
2 4
2 1
5 6

Sample Output2

2               //从1出发,长度为2的简单路径有2条:1->2->3,1->2->4。1->2->1不是,因为不是简单路径。

Limits

0<n,M<=10 0<=m<=100

数据保证合法

(PS:关于简单路径的起点终点是否能相同,这个有点争议。本题规定不能相同)

FineArtz's solution

/* Path */
#include <iostream>
using namespace std;

int n, m, start, len;
int head[15] = {0}, nxt[105] = {0}, e[105] = {0};
int cnt = 0, ans = 0;
bool vis[15] = {0};

void addEdge(int u, int v){
    nxt[++cnt] = head[u];
    e[cnt] = v;
    head[u] = cnt;
}

void dfs(int x, int step){
    if (step == len){
        ++ans;
        return;
    }
    for (int i = head[x]; i; i = nxt[i]){
        if (!vis[e[i]]){
            vis[e[i]] = true;
            dfs(e[i], step + 1);
            vis[e[i]] = false;
        }
    }
}

int main(){
    cin >> n >> m >> start >> len;
    for (int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }
    vis[start] = true;
    dfs(start, 0);
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

bool dfs_visited[20] = { 0 };

class graph_point {
public:
    int next[20] = { 0 };
    int edge_num = 0;

    void add_edge(int to) {
        //判断是否重复
        for (int i = 0; i < edge_num; ++i)
            if (next[i] == to)
                return;
        next[edge_num++] = to;
    }
};

graph_point graph[12];

int dfs(int start, int length) {
    if (dfs_visited[start])
        return 0;
    if (length == 0) {
        return 1;
    }
    dfs_visited[start] = true;
    int ans = 0;
    for (int i = 0; i < graph[start].edge_num; ++i)
        ans += dfs(graph[start].next[i], length - 1);
    dfs_visited[start] = false;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, start, M;
    cin >> n >> m >> start >> M;

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].add_edge(b);
    }

    cout << dfs(start, M);

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 10 + 10;

struct edgeNode {
    int data;
    edgeNode *next;

    edgeNode(int d = 0, edgeNode *n = 0) : data(d), next(n) {}
};

struct verNode {
    int data;
    edgeNode *head;

    verNode(int d = 0, edgeNode *h = 0) : data(d), head(h) {}
};

int n, m, start, M, temp1, temp2, ans = 0;
verNode *nodes[maxN];
bool isVisited[maxN] = {0};

void DFS(int i, int len);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> start >> M;

    for (int i = 1; i <= n; i++) {
        nodes[i] = new verNode(i);
    }

    for (int i = 0; i < m; i++) {
        cin >> temp1 >> temp2;
        bool flag = 1;
        edgeNode *p = nodes[temp1]->head;
        while (p) {
            if (p->data == temp2) {
                flag = 0;
                break;
            }
            p = p->next;
        }
        if (flag) {
            nodes[temp1]->head = new edgeNode(temp2, nodes[temp1]->head);
        }
    }

    DFS(start, 0);

    cout << ans;

    return 0;
}

void DFS(int i, int len) {
    if (isVisited[i]) {
        return;
    }
    isVisited[i] = 1;
    if (len == M) {
        ans++;
        isVisited[i] = 0;
        return;
    }
    edgeNode *p = nodes[i]->head;
    while (p) {
        DFS(p->data, len + 1);
        p = p->next;
    }
    isVisited[i] = 0;
}

yyong119's solution

#include <iostream>
#include <queue>
using namespace std;

int n, m, start, M, total;
bool visited[11];
queue<int> a[11];
void dfs(int depth, int pos) {

    if (depth == M + 1) {
        ++total;
        return;
    }
    queue<int> tmp = a[pos];
    while (!tmp.empty()) {
        int next = tmp.front();
        tmp.pop();
        if (!visited[next]) {
            visited[next] = true;
            dfs(depth + 1, next);
            visited[next] = false;
        }
    }
}

int main() {

    ios::sync_with_stdio(false);

    cin >> n >> m >> start >> M;
    for (int i = 1; i <= m; ++i) {
        int from, to;
        cin >> from >> to;
        a[from].push(to);
    }
    visited[start] = true;
    dfs(1, start);
    cout << total << endl;
    return 0;
}

Zsi-r's solution

#include <iostream>
using namespace std;

class graph
{
private:
    struct edgeNode
    {
        int end;
        edgeNode *next;
        edgeNode(int e, edgeNode *n = NULL) : end(e), next(n){};
    };

    int Vers, Edges,M;//the target to the length of path
    edgeNode **verList;

public:

    int dfs(int start, bool visited[],int currentlength) const
    {   
        int count = 0;
        edgeNode *p = verList[start];
        visited[start] = true;
        if (currentlength==M)
            return 1;
        while (p != NULL)
        {
            if (visited[p->end] == false)
            {
                count+= dfs(p->end, visited,currentlength+1);
                visited[p->end] = false;
            }
            p = p->next;
        }
        return count;
    }
/*
    int dfs(int start,bool visited[],int currentlength)
    {

    }
*/
public:
    graph(int vSize, int eSize,int Mtmp)
    {
        Vers = vSize;
        Edges = eSize;
        M = Mtmp;
        verList = new edgeNode*[vSize+1];
        for (int i = 0; i <= vSize; i++)
            verList[i] = NULL;
    }
    ~graph()
    {
        edgeNode *p;
        for (int i = 1; i <= Vers; i++)
        {
            p = verList[i];
            while (p != NULL)
            {
                verList[i] = p->next;
                delete p;
                p = verList[i];
            }
        }
        delete[] verList;
    }
    void insert(int x, int y)
    {
        verList[x]= new edgeNode(y, verList[x]);
    }

};

int main()
{
    int numofver, numofedge, startnode, goal,nodeofedge1,nodeofedge2;
    cin >> numofver >> numofedge >> startnode >> goal;
    graph gf(numofver, numofedge, goal);
    for (int i = 0; i < numofedge;i++)
    {
        cin >> nodeofedge1 >> nodeofedge2;
        gf.insert(nodeofedge1, nodeofedge2);
    }
    bool *visited = new bool[numofver+1];
    for (int i = 0; i <= numofver;i++)
        visited[i] = false;
    cout << gf.dfs(startnode, visited, 0)<<endl;
}