題意：一個包含<=20個結(jié)點的無向圖，輸入一個結(jié)點k，求從1到的k的所有路徑，要求字典序輸出，并且結(jié)點不能重復(fù)。

思路：剛開始直接回溯，結(jié)果超時了；從終點出發(fā)，找到所有與終點連通的結(jié)點，存儲在數(shù)組aa當(dāng)中，之后排序（字典序輸出嘛），這樣的話當(dāng)從起點無法到達(dá)終點時，減少了很多結(jié)點判斷（剪枝）。想象一下當(dāng)一個長度為20的路徑>10的時候有斷點，那么從起始位置1開始，肯定沒有與g[1][i]相連的路徑，很快就退出dfs了。

AC代碼如下：

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=20+2;int g[maxn][maxn];       //儲存無向圖 int vis[maxn],aa[maxn];  //aa用于存儲與目標(biāo)點k聯(lián)通的點集 int path[maxn];  //輸出路徑保存 （下標(biāo)從1開始） int k,total;int maxn2;void PRint(int tmp){	printf("%d",path[1]);	for(int i=2;i<=tmp;i++)	printf(" %d",path[i]);	printf("/n");}void dfs1(int cur){    //收集與目標(biāo)點k聯(lián)通的點集 	vis[cur]=1;	aa[maxn2++]=cur;	for(int i=1;i<=20;i++){		if(!vis[i] && g[cur][i])		dfs1(i);	}}void dfs(int cur,int tmp){   	if(cur==k){		print(tmp-1);		total++;		return ;	}	for(int i=0;i<=maxn2;i++){		if(g[cur][aa[i]] && !vis[aa[i]]){			vis[aa[i]]=1;			path[tmp]=aa[i];			dfs(aa[i],tmp+1);			vis[aa[i]]=0;		}	}}int main(){	int count1=0;	while(scanf("%d",&k)==1){		memset(g,0,sizeof(g));		memset(vis,0,sizeof(vis));		int a,b;		while(scanf("%d%d",&a,&b)==2 && a){			g[a][b]=1;			g[b][a]=1;	   }	   maxn2=total=0;	   dfs1(k);	   sort(aa,aa+maxn2);  //必須排序，題目要求字典序輸出 	   memset(vis,0,sizeof(vis));	   printf("CASE %d:/n",++count1);	   path[1]=vis[1]=1;	   dfs(1,2);	   printf("There are %d routes from the firestation to streetcorner %d./n",total,k);	}	return 0;}