Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <set>
- #include <vector>
- std::vector<std::vector<int> > graph;
- std::vector<int> answ;
- std::vector<int> odd_nodes;
- void DFS(int curr_node) {
- for (int i = 1; i != graph[curr_node].size(); ++i) {
- if (graph[curr_node][i] != 0) {
- --graph[curr_node][i];
- --graph[i][curr_node];
- DFS(i);
- answ.push_back(curr_node);
- }
- }
- }
- int main() {
- int n;
- std::cin >> n;
- graph.resize(n + 1);
- for (int i = 1; i != n + 1; ++i) {
- graph[i] = std::vector<int>(n + 1);
- }
- int num_odd_degree = 1;
- for (int i = 1; i != n + 1; ++i) {
- int count;
- std::cin >> count;
- for (int j = 0; j != count; ++j) {
- int second, weight;
- std::cin >> second >> weight;
- graph[i][second] += 1;
- }
- if (count % 2) {
- num_odd_degree = i;
- odd_nodes.push_back(i);
- }
- }
- DFS(num_odd_degree);
- std::cout << answ.size() << "\n";
- std::reverse(answ.begin(), answ.end());
- if (odd_nodes.size() == 0)
- answ.push_back(num_odd_degree);
- else if (num_odd_degree == odd_nodes[0])
- answ.push_back(odd_nodes[1]);
- else
- answ.push_back(odd_nodes[0]);
- for (auto elem : answ)
- std::cout << elem << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement