Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- // trip to new record: 2100 hard (last record: 1800)
- vector<vector<pair<int, int>>> g;
- vector<bool> used;
- vector<int> tin;
- vector<int> tup;
- int timer = 0;
- vector<int> ans;
- void dfs1(int v, int pr, int ind) { // dfs tree
- used[v] = 1;
- tin[v] = timer++;
- tup[v] = tin[v];
- for(int i = 0; i < g[v].size(); i++) {
- int to = g[v][i].first;
- if(g[v][i].second == ind) continue;
- if(!used[to]) {
- dfs1(to, v, g[v][i].second);
- tup[v] = min(tup[v], tup[to]);
- }
- else {
- tup[v] = min(tup[v], tin[to]);
- }
- }
- if(tin[pr] < tup[v]) {
- ans.push_back(ind);
- }
- }
- vector<bool> used3;
- int mx_ans = 0;
- int versh = 0;
- void dfs2(int v, int depth) { // 1 case
- if(depth > mx_ans) {
- mx_ans = depth;
- versh = v;
- }
- used3[v] = true;
- for(int i = 0; i < g[v].size(); i++) {
- int to = g[v][i].first;
- if(!used3[to]) {
- dfs2(to, ++depth);
- }
- }
- }
- vector<int> pr;
- vector<bool> used2;
- void dfs3(int v, int pred) { // 2 case
- used2[v] = true;
- for(int i = 0; i < g[v].size(); i++) {
- int to = g[v][i].first;
- if(to == pred) continue;
- if(!used2[to] && tup[to] == 0) {
- pr[to] = v;
- dfs3(to, v);
- }
- }
- int ver = v;
- vector<int> path;
- while(ver != 0) {
- path.push_back(ver);
- ver = pr[ver];
- }
- path.push_back(0);
- reverse(path.begin(), path.end());
- for(auto& i : path) i++;
- cout << path.size() << '\n';
- for(int i = 0; i < path.size(); i++) cout << path[i] << ' ';
- exit(0);
- }
- int main() {
- int n, m;
- cin >> n >> m;
- g.resize(n);
- tin.resize(n);
- tup.resize(n);
- used.resize(n);
- pr.resize(n);
- used2.resize(n);
- used3.resize(n);
- for(int i = 0; i < m; i++) {
- int a, b;
- cin >> a >> b;
- if(a > b) {
- swap(a, b);
- }
- a--;
- b--;
- g[a].push_back({b, i});
- g[b].push_back({a, i});
- }
- for(int i = 0; i < n; i++) {
- if(!used[i]) {
- dfs1(i, i, -1);
- }
- }
- if(count(tup.begin(), tup.end(), 0) == 1) {
- cout << -1 << '\n';
- dfs2(0, 0);
- cout << versh + 1;
- }
- else {
- dfs3(0, 0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement