Advertisement
achulkov2

Untitled

Apr 15th, 2018
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <set>
  4. #include <vector>
  5.  
  6. std::vector<std::vector<int> > graph;
  7. std::vector<int> answ;
  8. std::vector<int> odd_nodes;
  9.  
  10. void DFS(int curr_node) {
  11. for (int i = 1; i != graph[curr_node].size(); ++i) {
  12. if (graph[curr_node][i] != 0) {
  13. --graph[curr_node][i];
  14. --graph[i][curr_node];
  15. DFS(i);
  16. answ.push_back(curr_node);
  17. }
  18. }
  19. }
  20.  
  21. int main() {
  22. int n;
  23. std::cin >> n;
  24. graph.resize(n + 1);
  25. for (int i = 1; i != n + 1; ++i) {
  26. graph[i] = std::vector<int>(n + 1);
  27. }
  28. int num_odd_degree = 1;
  29. for (int i = 1; i != n + 1; ++i) {
  30. int count;
  31. std::cin >> count;
  32. for (int j = 0; j != count; ++j) {
  33. int second, weight;
  34. std::cin >> second >> weight;
  35. graph[i][second] += 1;
  36. }
  37. if (count % 2) {
  38. num_odd_degree = i;
  39. odd_nodes.push_back(i);
  40. }
  41. }
  42. DFS(num_odd_degree);
  43. std::cout << answ.size() << "\n";
  44. std::reverse(answ.begin(), answ.end());
  45. if (odd_nodes.size() == 0)
  46. answ.push_back(num_odd_degree);
  47. else if (num_odd_degree == odd_nodes[0])
  48. answ.push_back(odd_nodes[1]);
  49. else
  50. answ.push_back(odd_nodes[0]);
  51. for (auto elem : answ)
  52. std::cout << elem << " ";
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement