dfs.cpp

来自「自作的浏览器」· C++ 代码 · 共 69 行

#include<iostream>
#define maxn 20
using namespace std;

bool edge[maxn][maxn];
bool flag[maxn];
int traval[maxn];
int n;

void init()
{
   int i,j,u,v,m;
   scanf("%d%d",&n,&m);
   memset(edge,false,sizeof(edge));
   while(m--)
   {
       scanf("%d%d",&u,&v);
       edge[u][v]=true;      
   }  
   return ;   
}

void dfs(int t,int d)
{
     int i; 
  traval[d]=t;   
   if(d==n-1)
   {
      if(traval[n-1]==n-1)
      {
      for(i=0;i<n;i++)
      cout<<traval[i]<<" ";
      cout<<endl; 
      }  
      return ;     
   }
  
   for(i=1;i<n;i++)
   if(!flag[i]&&edge[t][i])
   {
      flag[i]=true;
      dfs(i,d+1);
      flag[i]=false;            
   }
   return ;
}
void solve()
{
   int i;
   memset(flag,false,sizeof(flag)); 
   flag[0]=true;
   traval[0]=0;
   for(i=1;i<n;i++)
   if(edge[0][i])
   {
   flag[i]=true;
   dfs(i,1);
   flag[i]=false;
   }
   return ;    
}
int main()
{
   init();
   solve();
   system("pause");
   return 0;  
}