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