Advertisement
fast_turtle

Untitled

Dec 8th, 2022
478
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 212345;
  4. set <int> a, b;
  5. vector <int> path;
  6. int marc[MAXN];
  7. vector <int> grafo[MAXN];
  8. bool dfs(int v) {
  9.     marc[v] = 1;
  10.     a.erase(v); path.push_back(v);
  11.     if(a.size() == b.size()) return true;
  12.     for(int i = 0; i < grafo[v].size(); i++) {
  13.         int viz = grafo[v][i];
  14.         if(marc[viz] == 1) continue;
  15.         if(dfs(viz)) return true;
  16.     }
  17.     path.pop_back(); b.insert(v);
  18.     if(a.size() == b.size()) return true;
  19.     return false;
  20. }
  21. int main() {
  22.     int n, m;
  23.     scanf("%d %d", &n, &m);
  24.     for(int i = 1; i <= n; i++) a.insert(i);
  25.     for(int i = 0; i < m; i++) {
  26.         int a, b;
  27.         scanf("%d %d", &a, &b);
  28.         grafo[a].push_back(b); grafo[b].push_back(a);
  29.     }
  30.     dfs(1);
  31.     printf("%d %d\n", path.size(), a.size());
  32.     for(int i = 0; i < path.size(); i++) printf("%d ", path[i]);
  33.     printf("\n");
  34.     set <int> :: iterator it;
  35.     for(it = a.begin(); it != a.end(); it++) printf("%d ", *it);
  36.     printf("\n");
  37.     for(it = b.begin(); it != b.end(); it++) printf("%d ", *it);
  38.     printf("\n");
  39.     return 0;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement