daily pastebin goal
56%
SHARE
TWEET

Untitled

a guest Jan 21st, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2.  
  3. using namespace std;
  4. ifstream f("date.in");
  5. ofstream g("date.out");
  6.  
  7. int s[100],n,m,a[100][100];
  8.  
  9. void init(int k)
  10. {
  11.     s[k]=0;
  12. }
  13. int succesor(int k)
  14. {
  15.     s[k]++;
  16.     if(s[k]<=n)
  17.         return 1;
  18.     return 0;
  19. }
  20. int valid(int k)
  21. {
  22.     for(int i=1;i<k;i++)
  23.     {
  24.         if(s[i]==s[k])
  25.             return 0;
  26.     }
  27.     if(k>1)
  28.     {
  29.         if(a[s[k-1]][s[k]]==0)
  30.             return 0;
  31.     }
  32.     return 1;
  33. }
  34. int solutie(int k)
  35. {
  36.     if(k==n&& a[s[1]][s[k]]==1)
  37.         return 1;
  38.     return 0;
  39. }
  40. void tiparire(int k)
  41. {
  42.     for(int i=1;i<=k;i++)
  43.         g<<s[i]<<" ";
  44. }
  45. int backtracking(int k)
  46. {
  47.     int ok1,ok2;
  48.     init(k);
  49.     while(k>1)
  50.     {
  51.         do
  52.         {
  53.             ok1=succesor(k);
  54.             ok2=valid(k);
  55.         }while(ok1&&!ok2);
  56.         if(ok1)
  57.         {
  58.             if(solutie(k))
  59.                {
  60.                    tiparire(k);
  61.                    return 0;
  62.                }
  63.             else
  64.             {
  65.                 k++;
  66.                 init(k);
  67.             }
  68.         }
  69.         else
  70.             k--;
  71. }}
  72.  
  73. int main()
  74. {
  75.     int i,c,d;
  76.     f>>n>>m;
  77.     for(i=1;i<=m;i++)
  78.     {
  79.         f>>c>>d;
  80.         a[c][d]=1;
  81.         a[d][c]=1;
  82.     }
  83.     backtracking(1);
  84.     return 0;
  85. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top