# 11233: 【原1233】Path

### 题目描述

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

## 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};

e[cnt] = v;
}

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;
}
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;

//判断是否重复
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;
}

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;

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;
while (p) {
if (p->data == temp2) {
flag = 0;
break;
}
p = p->next;
}
if (flag) {
}
}

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;
}
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;
}
``````