Advertisement
cojoc

Untitled

May 23rd, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.80 KB | None | 0 0
  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4.  
  5. int G[100][100];
  6. int n;
  7. int coada[100];
  8. int start;
  9. int sfarsit;
  10. int vizitat[100];
  11. int nod_start;
  12. int grad_noduri[100];
  13. int k=0;
  14.  
  15. int read_data()
  16. {
  17. fstream f("input.in", ios::in);
  18. f>>n;
  19. for(int i=1; i<n; i++)
  20. for(int j=1; j<=n; j++)
  21. f>>G[i][j];
  22.  
  23. return 0;
  24. }
  25.  
  26. int grad()
  27. {
  28. int suma;
  29. for(int i=1; i<=n; i++)
  30. {
  31. suma=0;
  32. for(int j=1; j<=n; j++)
  33. {
  34. suma=suma+G[i][j];
  35. }
  36. grad_noduri[i]=suma;
  37. }
  38. return 0;
  39. }
  40.  
  41. int nr_noduri_vizitate()
  42. {
  43. int viz=0;
  44. for(int i=1; i<=n; i++)
  45. {
  46. if(vizitat[i]) viz++;
  47. }
  48. return viz;
  49. }
  50.  
  51. int BFS(int nume_nod)
  52. {
  53. start=1;
  54. sfarsit=1;
  55. coada[start]=nume_nod;
  56. while(start<=sfarsit)
  57. {
  58. //cout<<coada[start]<<", ";
  59. vizitat[coada[start]]=1;
  60. for(int i=1; i<=n; i++)
  61. {
  62. if((G[coada[start]][i]!=0) && (vizitat[i]==0))
  63. {
  64. sfarsit++;
  65. coada[sfarsit]=i;
  66. vizitat[i]=1;
  67. }
  68. }
  69. start++;
  70. }
  71. return 0;
  72. }
  73. int vizitati=1;
  74. int nightmare_cycle(int nod)
  75. {
  76. for(int i=1; i<=n; i++)
  77. if(vizitat[i]==0)vizitati = 0;
  78.  
  79. if(vizitati==0)
  80. cout<<nod<<" ";
  81. for(int i=1; i<=n; i++)
  82. {
  83. if(G[nod][i]==1)
  84. {
  85. G[nod][i]=0;
  86. G[i][nod]=0;
  87. vizitat[i]=1;
  88.  
  89. BFS(i);
  90. if(nr_noduri_vizitate()==(n-k)) nightmare_cycle(i);
  91. else
  92. {
  93. G[i][nod]=1;
  94. G[nod][i]=1;
  95. vizitat[i]=0;
  96. }
  97. }
  98. }
  99. return 0;
  100. }
  101.  
  102. int main()
  103. {
  104. read_data();
  105. nightmare_cycle(1);
  106. return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement