AGC013 B問題 Hamiltonish Path

問題

agc013.contest.atcoder.jp

解説

まず適当に頂点uを選択します。頂点uから移動可能な頂点vを探して頂点vから今まで訪れた頂点でない頂点xを選択し頂点xから移動可能な今まで訪れた頂点でない頂点yを選択し、、、
このような操作を繰り返していくと移動できなくなる頂点にたどり着くことができ、その頂点は片方の端点になります。そして再び頂点uから移動可能な今まで訪れた頂点でない頂点zを選択し、、、のように繰り返すと、別の片方の端点にたどり着くことができます。したがって移動可能な頂点を探していく過程で頂点を順番通り保持していけば解を求めることができます。

コード

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
 
#define ALL(x) x.begin(), x.end()
using namespace std;
 
typedef vector<vector<int> > G;
const int inf = 1e9;
 
int n, m;
G graph;
vector<int> ans;
 
int visited[100100];
 
void dfs(int u){
 
    ans.push_back(u);
    visited[u] = 1;
 
    for(int i=0; i<graph[u].size(); i++){
        int v = graph[u][i];
        if( !( visited[v] ) ){
            return dfs(v);
        }
    }
    return;
}
 
int main(void){
    cin >> n >> m;
    graph = G(n+100);
    for(int i=0; i<m; i++){
 
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
 
    }
    
    dfs(1);
    reverse(ans.begin(), ans.end());
    ans.pop_back();
    dfs(1);
 
    cout << ans.size() << endl;
 
    for(int i=0; i<ans.size(); i++){
        cout << ans[i] << " ";
    }
 
    cout << endl;
    return 0;
}