Advertisement
Guest User

graf aciclic

a guest
Dec 12th, 2019
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, este=0, x;
  6. //int m[100][100];
  7.  
  8. //vector < vector < int > > m(101, vector < int >(101));
  9. vector<int> m[101];
  10. vector < int > st(101);
  11. void Citire()
  12. {
  13.     ifstream fin("graf.in");
  14.     int a,x,y;
  15.     fin>>n>>a;
  16.     for(int i = 0; i < a; i++)
  17.     {
  18.         fin>>x>>y;
  19. //        m[x][y] = 1;
  20. //        m[y][x] = 1;
  21.         m[x].push_back(y);
  22.         m[y].push_back(x);
  23.     }
  24.     fin.close();
  25. }
  26.  
  27. void init(int k)
  28. {
  29.     st[k]=0;
  30. }
  31.  
  32. int succesor(int k)
  33. {
  34.     if(st[k] < n)
  35.     {
  36.         st[k]++;
  37.         return 1;
  38.     }
  39.     return 0;
  40. }
  41.  
  42. int valid(int k)
  43. {
  44.     if(k>1)
  45.         if(m[st[k-1]][st[k]] == 0)
  46.             return 0;
  47.  
  48.     for(int i=2; i<k; i++)
  49.         if(st[k] == st[i])
  50.             return 0;
  51.  
  52.     return 1;
  53. }
  54.  
  55.  
  56. int solutie(int k)
  57. {
  58.     return st[k]==st[1];
  59. }
  60.  
  61.  
  62. void tipar(int k)
  63. {
  64.     for(int i=1, este=1; i<=k; i++)
  65.         cout<<st[i]<<" ";
  66.     cout<<endl;
  67. //    if(k>1)
  68. //        este=1;
  69. }
  70.  
  71. void bkt(int k)
  72. {
  73.     init(k);
  74.     while(succesor(k))
  75.         if(valid(k))
  76.             if(solutie(k))
  77.                 tipar(k);
  78.             else
  79.                 bkt(k+1);
  80. }
  81.  
  82. int main()
  83. {
  84.     Citire();
  85.     for(int i=1;i<=n;i++)
  86.     {
  87.         st[1]=i;
  88.         este=0;
  89.         bkt(1);
  90.         if(este == 1)
  91.         {
  92.             cout<<"";
  93.             return 0;
  94.         }
  95.     }
  96.     cout<<"Aciclic";
  97.     return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement