Advertisement
monyca98

graf partial

May 27th, 2016
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.93 KB | None | 0 0
  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4. ifstream f("e:\\info\\backtracking\\grafpartial.txt");
  5. int nr=0;
  6. void citire(int a[20][20],int m)
  7. { int i,j;
  8. for(int k=1;k<=m;k++)
  9. { f>>i>>j;
  10. a[i][j]=1;
  11. a[j][i]=1;
  12. }
  13. }
  14. void afisare(int a[20][20],int n)
  15. { for(int i=1;i<=n;i++)
  16. { for(int j=1;j<=n;j++)
  17. cout<<a[i][j]<<" ";
  18. cout<<endl;
  19. }
  20. }
  21. void transformare(int b[20][20],int a[20][20],int n)
  22. { int i,j,k=1;
  23. for(i=1;i<=n;i++)
  24. for(j=1;j<=i;j++)
  25. if(a[i][j]==1)
  26. { b[i][k]=1;
  27. b[j][k]=1;
  28. k++;
  29. }
  30. }
  31. int succesor(int st[20],int k,int m)
  32. { if(st[k]<m)
  33. { st[k]++;
  34. return 1;
  35. }
  36. else
  37. return 0;
  38. }
  39. int valid(int st[20],int k)
  40. { for(int i=1;i<k;i++)
  41. if(st[k]==st[i])
  42. return 0;
  43. if(k>1 && st[k]<st[k-1])
  44. return 0;
  45. return 1;
  46. }
  47. void tipar(int st[20],int p,int n,int b[20][20])
  48. { nr++;
  49. cout<<"graful partial "<<nr<<" are ";
  50. cout<<" muchiile:";
  51. for(int i=1;i<=p;i++)
  52. { for(int j=1;j<=n;j++)
  53. if(b[j][st[i]]==1)
  54. cout<<j<<" ";
  55. cout<<";";
  56. }
  57. cout<<endl;
  58. }
  59. void bt(int k,int st[20],int n,int m,int p,int b[20][20])
  60. { int as,ev;
  61. k=1;
  62. st[k]=0;
  63. while(k>0)
  64. { as=1;
  65. ev=0;
  66. while(as && !ev)
  67. { as=succesor(st,k,m);
  68. if(as)
  69. ev=valid(st,k);
  70. }
  71. if(as)
  72. if(k==p)
  73. { tipar(st,p,n,b);
  74. nr++;
  75. }
  76. else
  77. { k++;
  78. st[k]=0;
  79. }
  80. else
  81. k--;
  82. }
  83. }
  84. int main()
  85. { int nr=0,a[20][20]={0},b[20][20],k,n,m,p,st[20];
  86. f>>n>>m;
  87. citire(a,m);
  88. afisare(a,n);
  89. transformare(b,a,n);
  90. for(p=m;p>=0;p--)
  91. bt(k,st,n,m,p,b);
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement