题目链接：http://lx.lanqiao.cn/problem.page?gpid=T36
历届试题 网络寻路 时间限制：1.0s 内存限制：256.0MB 问题描述
X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包，为了安全起见，必须恰好被转发两次到达目的地。该包可能在任意一个节点产生，我们需要知道该网络中一共有多少种不同的转发路径。
源地址和目标地址可以相同，但中间节点必须不同。
如下图所示的网络。
1 -> 2 -> 3 -> 1 是允许的
1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。
输入格式输入数据的第一行为两个整数N M，分别表示节点个数和连接线路的条数(1<=N<=10000; 0<=M<=100000)。
接下去有M行，每行为两个整数 u 和 v，表示节点u 和 v 联通(1<=u,v<=N , u!=v)。
输入数据保证任意两点最多只有一条边连接，并且没有自己连自己的边，即不存在重边和自环。
输出格式 输出一个整数，表示满足要求的路径条数。 样例输入1 3 3 1 2 2 3 1 3 样例输出1 6 样例输入2 4 4 1 2 2 3 3 1 1 4 样例输出2 10
这题和危险系数那篇一样的，都是用邻接表存储边
思路就是：用邻接表存储边，以每一个点分别为起点，然后进行n次dfs()，dfs()求每次以一个点为起点时的路径条数
然后下面的代码，第一篇是我自己写的，第二篇是借鉴的别人的，思路都差不多，不过dfs()处理条件不太一样 先说我的思路，深搜链接两条边的每个点，然后当经过两个点时，再计算第二个点的出边的个数就是本次搜索的个数，然后回溯，当然要减去从经过的第一个点到第二个点的这条边（不能再从第二个点走向第一个点了） 第二个思路需要注意的是：正常来说，对下一个点，我们就要取没有标记的进行搜索，但是当搜到第二个点时，下一个点回到最初的起始点也是可以的，这个需要判断，其余的正常搜就行，，还要注意如果再次搜到了第一个点，那么回溯时不要取消标记（第一个点是起始点嘛）
AC代码：
one：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node { int v,next; } e[100005]; int head[10005],vis[10005]; int n,m,x,y,num,ans; void init(int u,int v) { e[num].v=v; e[num].next=head[u]; head[u]=num++; } void dfs(int s,int step) { int i; if(step==2) { for(i=head[s]; i!=-1; i=e[i].next) ans++; ans--; return ; } for(i=head[s]; i!=-1; i=e[i].next) { if(vis[e[i].v]) continue; vis[e[i].v]=1; dfs(e[i].v,step+1); vis[e[i].v]=0; } } int main() { int i,j; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(i=0; i<m; i++) { scanf("%d%d",&x,&y); init(x,y); init(y,x); } for(i=1; i<=n; i++) { memset(vis,0,sizeof(vis));//重复dfs()时记得初始化。。。。现在总是犯这些毛病 vis[i]=1;//记得第一个数字标记啊，这儿也困了我很久 dfs(i,0); } printf("%d\n",ans); return 0; } </cstring></cstdio></iostream>
two:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node { int v,next; } e[100005]; int head[10005],vis[10005]; int n,m,x,y,num,ans; void init(int u,int v) { e[num].v=v; e[num].next=head[u]; head[u]=num++; } void dfs(int s,int step,int pos) { int i; if(step==3) { ans++; return ; } for(i=head[s]; i!=-1; i=e[i].next) { if(!vis[e[i].v]||(e[i].v==pos&&step==2)) { vis[e[i].v]=1; dfs(e[i].v,step+1,pos); if(e[i].v!=pos)//第一个不用取消标记 vis[e[i].v]=0; } } } int main() { int i; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(i=0; i<m; i++) { scanf("%d%d",&x,&y); init(x,y); init(y,x); } for(i=1; i<=n; i++) { memset(vis,0,sizeof(vis)); vis[i]=1; dfs(i,0,i); } printf("%d\n",ans); return 0; } </cstring></cstdio></iostream>
