本文共 1705 字，大约阅读时间需要 5 分钟。

题目：

输入一个n(n<=20)个结点的无向图以及某个节点k，按照字典序从小到大排序输出从结点1到结点k的所有路径，要求结点不能重复经过。

注意：

要事先判断1到k是否连通。

思路：

判断连通可以通过并查集判断它们是否在同一个集合中。

然后就是dfs找路径了。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int t=0;int n;int a[25][25];int vis[25];int b[25];int num;int ans[25];int rot;int Find(int x){    if(x==b[x]) return x;    return b[x]=Find(b[x]);}void dfs(int tnum,int x){    ans[tnum]=x;    vis[x]=1;    if(x==n)    {        rot++;        for (int i=0;i<=tnum;i++)            printf("%d%c",ans[i],i==tnum?'\n':' ');        return;    }    for (int i=1;i<=20;i++)    {        if(a[x][i]&&!vis[i])        {            dfs(tnum+1,i);            vis[i]=0;        }    }}int main(){    while (scanf("%d",&n)!=EOF)    {        rot=0;        t++;        for (int i=1;i<25;i++) b[i]=i;        memset (vis,0,sizeof(vis));        memset (a,0,sizeof(a));        num=0;        int x,y;        while (scanf("%d%d",&x,&y))        {            if(x==0&&y==0) break;            if(!vis[x])            {                num++;                vis[x]=1;            }            if(!vis[y])            {                num++;                vis[y]=1;            }            a[x][y]=1;            a[y][x]=1;            int px=Find(x);            int py=Find(y);            b[px]=py;        }        int p1=Find(1);        int p2=Find(n);        printf("CASE %d:\n",t);        if(p1!=p2)        {            printf("There are 0 routes from the firestation to streetcorner %d.\n",n);            continue;        }        memset(vis,0,sizeof(vis));        dfs(0,1);        printf("There are %d routes from the firestation to streetcorner %d.\n",rot,n);    }    return 0;}
       
      
     
    
   

转载地址：http://twoen.baihongyu.com/