Advertisement
Ancutahij

Det. ciclurilor elem. intr-un graf

Apr 6th, 2016
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. #include<fstream.h>
  2. ifstream f("d:\\elev\\mat.txt");
  3. void citire(int a[20][20],int m)
  4. {   int i,j;
  5.     for(int  k=1;k<=m;k++)
  6.     {   f>>i>>j;
  7.         a[i][j]=1;
  8.         a[j][i]=1;
  9.     }
  10. }
  11.  void afisare(int a[20][20],int n)
  12.  {  for(int i=1;i<=n;i++)
  13.     {   for(int j=1;j<=n;j++)
  14.             cout<<a[i][j]<<" ";
  15.         cout<<endl;
  16.     }
  17.  }
  18. int succesor(int st[20],int n,int k)
  19. {   if(st[k]<n)
  20.     {   st[k]++;
  21.         return 1;}
  22.      else
  23.         return 0;
  24. }
  25. int valid(int st[20],int k,int a[20][20])
  26. {  
  27.     for(int i=1;i<k;i++)
  28.     if(st[i]==st[k])
  29.            return 0;
  30.     if(a[st[k]][st[k-1]]==0 && k>1)
  31.             return 0;
  32.     return 1;
  33. }
  34. void tipar(int st[20], int k,int x)
  35. {   for(int i=1;i<=k;i++)
  36.     cout<<st[i]<<" ";
  37.     cout<<x;
  38.     cout<<endl;
  39. }
  40. void bt(int st[20],int n,int k,int a[20][20],int x)
  41. {   int nr=0,as,ev;
  42.     k=2;
  43.     st[k]=0;
  44.     while(k>1)
  45.     {   as=1;
  46.         ev=0;
  47.         while(as && !ev)
  48.         {   as=succesor(st,n,k);
  49.             if(as)ev=valid(st,k,a);}
  50.     if(as)
  51.             if(a[st[k]][x]==1 && k>2 )
  52.             {   tipar(st,k,x);
  53.                 nr++;}
  54.             else
  55.             {   k++;
  56.                 st[k]=0;}
  57.         else
  58.      k--;
  59.         }
  60.     cout<<"numarul de solutii sunt "<<nr<<" ";
  61.     cout<<endl;
  62. }
  63. void main ()
  64. {int st[20],n,k,a[20][20],x,y,b,m;
  65.  f>>n;
  66.  f>>m;
  67. citire(a,m);
  68. afisare(a,n);
  69. for(x=1;x<=n;x++)
  70.       {cout<<endl;
  71.        cin>>b;
  72.        st[1]=x;
  73.            bt(st,n,k,a,x);  
  74.          }
  75.      }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement