Advertisement
Guest User

graf aciclic 2

a guest
Dec 12th, 2019
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, este, x;
  6. int m[100][100], st[100]={0};
  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 && 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] && k>3;
  59. }
  60.  
  61.  
  62. void tipar(int k)
  63. {
  64.     este =1;
  65.     for(int i=1; i<=k; i++)
  66.         cout<<st[i]<<" ";
  67.     cout<<endl;
  68. //    if(k>1)
  69. //        este=1;
  70. }
  71.  
  72. void bkt(int k)
  73. {
  74.     init(k);
  75.     while(succesor(k))
  76.         if(valid(k))
  77.             if(solutie(k))
  78.                 tipar(k);
  79.             else
  80.                 bkt(k+1);
  81. }
  82.  
  83. int main()
  84. {
  85.     Citire();
  86.     for(int i=1;i<=n;i++)
  87.     {
  88.         st[1]=i;
  89.         este=0;
  90.         bkt(2);
  91.         if(este == 1)
  92.         {
  93.             cout<<"are cicluri";
  94.             return 0;
  95.         }
  96.     }
  97.     cout<<"Aciclic";
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement