网络寻路

末蓝、 2022-08-02 12:40 190阅读 0赞

X国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包，为了安全起见，必须恰好被转发两次到达目的地。该包可能在任意一个节点产生，我们需要知道该网络中一共有多少种不同的转发路径。

源地址和目标地址可以相同，但中间节点必须不同。

如图1所示的网络。

![Center][]

1 -> 2 -> 3 -> 1  是允许的

1 -> 2 -> 1-> 2 或者1->2->3->2 都是非法的。

输入数据的第一行为两个整数NM，分别表示节点个数和连接线路的条数(1<=N<=10000; 0<=M<=100000)。

接下去有M行，每行为两个整数 u 和 v，表示节点u 和 v联通(1<=u,v<=N , u!=v)。

输入数据保证任意两点最多只有一条边连接，并且没有自己连自己的边，即不存在重边和自环。

输出一个整数，表示满足要求的路径条数。

例如：

用户输入：

3 3

1 2

2 3

1 3

则程序应该输出：

再例如：

用户输入：

4 4

1 2

2 3

3 1

1 4

则程序应该输出：

资源约定：

峰值内存消耗 < 64M

CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...”的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0

注意: 只使用ANSI C/ANSI C++标准，不要调用依赖于编译环境或操作系统的特殊函数。

注意: 所有依赖的函数必须明确地在源文件中\#include <xxx>， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型(千万不要混淆c和cpp)。

参考代码：

#include<stdio.h>
    	#include<stdlib.h>
    	int m,n;
    	int **a;
    	int b[4];
    	int count=0;
    	
    	int place(int t){
    		int i,flag,j;
    		int*c;
    		c=(int*)malloc(sizeof(int)*(m+1));
    		
    		for(i=0;i<m+1;i++)
    			c[i]=0;
    			
    		for(i=0;i<=t&&i<3;i++)
    			c[b[i]]++;
    		for(i=0;i<=m;i++)
    			if(c[i]>1)
    				return 0;
    		
    		if(t>0){
    			flag=0;
    			for(j=0;j<n;j++){
    				if((a[j][0]==b[t-1]&&a[j][1]==b[t])||(a[j][1]==b[t-1]&&a[j][0]==b[t])){
    					flag=1;
    					break;
    				}
    			}
    			if(flag==0)
    				return 0;
    		}
    		
    		if(t==3)
    			for(i=1;i<3;i++)
    				if(b[i]==b[t])
    					return 0;
    		return 1;
    	}
    	
    	void backtrack(int t){
    		int i;
    		if(t==4){
    			for(i=0;i<4;i++)
    				printf("%d\t",b[i]);
    			printf("\n");
    			count++;
    		}else{
    			for(i=1;i<=m;i++){
    				b[t]=i;
    				if(place(t)){
    					backtrack(t+1);
    				}
    			}
    		}
    	}
    	int main(){
    		int i;
    		
    		scanf("%d%d",&m,&n);
    		
    		a=(int**)malloc(sizeof(int*)*n);
    		for(i=0;i<n;i++){
    			a[i]=(int*)malloc(sizeof(int)*2);
    			scanf("%d%d",a[i]+0,a[i]+1);
    		}
    		
    		backtrack(0);
    		
    		printf("%d\n",count);
    		return 0;
    
    }

![SouthEast][] ![SouthEast 1][]

[Center]: /images/20220731/f532b1de827e48c3812ebb91eb5d6a4a.png
[SouthEast]: https://img-blog.csdn.net/20150719223119158?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: /images/20220731/4a52a050ea244bc9bb8f1530c973d23b.png