Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 212345;
- set <int> a, b;
- vector <int> path;
- int marc[MAXN];
- vector <int> grafo[MAXN];
- bool dfs(int v) {
- marc[v] = 1;
- a.erase(v); path.push_back(v);
- if(a.size() == b.size()) return true;
- for(int i = 0; i < grafo[v].size(); i++) {
- int viz = grafo[v][i];
- if(marc[viz] == 1) continue;
- if(dfs(viz)) return true;
- }
- path.pop_back(); b.insert(v);
- if(a.size() == b.size()) return true;
- return false;
- }
- int main() {
- int n, m;
- scanf("%d %d", &n, &m);
- for(int i = 1; i <= n; i++) a.insert(i);
- for(int i = 0; i < m; i++) {
- int a, b;
- scanf("%d %d", &a, &b);
- grafo[a].push_back(b); grafo[b].push_back(a);
- }
- dfs(1);
- printf("%d %d\n", path.size(), a.size());
- for(int i = 0; i < path.size(); i++) printf("%d ", path[i]);
- printf("\n");
- set <int> :: iterator it;
- for(it = a.begin(); it != a.end(); it++) printf("%d ", *it);
- printf("\n");
- for(it = b.begin(); it != b.end(); it++) printf("%d ", *it);
- printf("\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement