Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int X[100002], Y[100002], n, m;
  6. /// (X[i], Y[i]) - muchie din graf
  7.  
  8. vector<int> L[100002];
  9. /// L[i] = indicii muchiilor incidente cu i
  10.  
  11. int viz[100002]; /// viz este pentru MUCHIILE deja vizitate
  12.  
  13. int t[100002]; /// verificarea conexitatii
  14.  
  15. int q[100002], ind; /// memorez ciclul eulerian
  16.  
  17. ifstream fin("euler.in");
  18. ofstream fout("euler.out");
  19.  
  20. void Citire()
  21. {
  22. int i, j;
  23. fin >> n;
  24. m = 0;
  25. while(fin >> i >> j)
  26. {
  27. m++;
  28. X[m] = i;
  29. Y[m] = j;
  30. L[i].push_back(m);
  31. L[j].push_back(m);
  32. }
  33. }
  34.  
  35. void DFS(int k)
  36. {
  37. int i;
  38. for(auto i : L[k])
  39. if(viz[i] == 0) /// muchia i este nevizitata
  40. {
  41. viz[i] = 1;
  42. DFS(X[i] + Y[i] - k);
  43. }
  44. q[++ind] = k;
  45. }
  46.  
  47. void DFS1(int k)
  48. {
  49. int i, j;
  50. t[k] = 1;
  51. for(i=0; i<L[k].size(); i++)
  52. {
  53. j = L[k][i];
  54. if(t[j] == 0) DFS1(j);
  55. }
  56. }
  57.  
  58. int ToateGradelePare()
  59. {
  60. int i;
  61. for(i=1; i<=n; i++)
  62. if(L[i].size() % 2 == 1) return 0;
  63. return 1;
  64. }
  65.  
  66. int EsteEulerian()
  67. {
  68. int i;
  69. if(!ToateGradelePare()) return 0;
  70. DFS1(1);
  71. /// Caut noduri nevizitate de grad nenul
  72. for(i=1; i<=n; i++)
  73. if(t[i] == 0 && L[i].size() > 0) return 0;
  74. return 1;
  75. }
  76.  
  77. int main()
  78. {
  79. int i;
  80. Citire();
  81. if(!EsteEulerian()) fout << "-1";
  82. else
  83. {
  84. DFS(1);
  85. fout << ind << endl;
  86. for(i=1; i<=ind; i++)
  87. fout << q[i] << " ";
  88. }
  89. return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement