Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int a[1000][1000],n,st[1000],k;
  5.  
  6. void init(){
  7. st[k]=0;
  8. }
  9.  
  10. int succesor(){
  11. if(st[k]<n){
  12. st[k]++;
  13. return 1;
  14. }
  15. return 0;
  16. }
  17.  
  18. int valid(){
  19. if(k>1)
  20. if(a[st[k-1]][st[k]]==0)
  21. return 0;
  22. for(int i=1;i<k;i++)
  23. if(st[k]==st[i])
  24. return 0;
  25. return 1;
  26. }
  27.  
  28. int solutie(){
  29. return k==n;
  30. }
  31.  
  32. void afisare(){
  33. for(int i=1;i<=k;i++)
  34. cout<<st[i]<<" ";
  35. cout<<endl;
  36. }
  37.  
  38. int backtraking(){
  39. k=1;
  40. int as;
  41. init();
  42. while(k>0)
  43. {
  44. as=succesor();
  45. while(as)
  46. {
  47. if(valid())
  48. if(solutie()){
  49. afisare();
  50. return 1;
  51. }
  52. else
  53. {
  54. k++;
  55. init();
  56. }
  57. as=succesor();
  58. }
  59. k--;
  60. }
  61. }
  62.  
  63. int main(){
  64. int m,x,y;
  65. cin>>n;
  66. m=(n*(n-1))/2;
  67. while(m){
  68. cin>>x>>y;
  69. a[x][y]=1;
  70. m--;
  71. }
  72. backtraking();
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement