題目大意：給出一個無邊權無向圖，起始結點為1，終止結點為t，求出從1到t的全部路徑。
先求出和t屬于同一個連通分量的結點，然后DFS。
以下是我的代碼：
#include<stdio.h>
#include<string.h>
#define maxn 1007
#define max(a,b) (a>b?a:b)
long cas,aim,n,m,ans,a[maxn],way[maxn];
bool g[maxn][maxn],used[maxn];
void swap(long &a,long &b)
{
long t=a;a=b;b=t;
}
void travel(long node)
{
used[node]=true;
m++;
a[m]=node;
for(long i=1;i<=n;i++)
if(!used[i]&&g[node][i])
travel(i);
}
void Qsort(long *a,long begin,long end)
{
long i=begin,j=end,mid=a[(begin+end)/2];
do{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++;j--;
}
}while(i<=j);
if(begin<j) Qsort(a,begin,j);
if(i<end) Qsort(a,i,end);
}
void dfs(long node,long dep)
{
if(node==aim)
{
bool first=true;
for(long i=1;i<=dep;i++)
{
if(first) first=false;
else printf(" ");
printf("%ld",way[i]);
}
putchar('\n');
ans++;
return;
}
for(long i=1;i<=m;i++)
if(!used[a[i]]&&g[node][a[i]])
{
way[dep+1]=a[i];
used[a[i]]=true;
dfs(a[i],dep+1);
used[a[i]]=false;
}
}
int main()
{
long s,t;
cas=0;
while(scanf("%ld",&aim)==1)
{
cas++;
n=ans=0;
memset(g,false,sizeof(g));
while(scanf("%ld%ld",&s,&t)==2)
{
if(s==0&&t==0) break;
n=max(n,s);n=max(n,t);
g[s][t]=g[t][s]=true;
}
memset(used,false,sizeof(used));
m=0;
travel(aim);
Qsort(a,1,m);
memset(way,0,sizeof(way));
memset(used,false,sizeof(used));
used[1]=true;
way[1]=1;
printf("CASE %ld:\n",cas);
dfs(1,1);
printf("There are %ld routes from the firestation to streetcorner %ld.\n",ans,aim);
}
return 0;
}
posted on 2010-03-20 12:03
lee1r 閱讀(487)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索