Submission #56676542

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)

int N,X,Y;
vector<vector<int>> nodeLists(200010,vector<int>(0));
vector<bool> isReached(200010,false);
deque<int> pathStack; // stackとして使う
// (最後に0からの値を表示するため stack では無理)
bool stop = false; // 探索を止めるためのフラグ

void searchPath(int from, int to) {
    if (!stop) pathStack.push_back(from);
    if (from == to) stop=true;
    isReached.at(from) = true;
    for(int i=0; i<(int)nodeLists.at(from).size(); i++) {
        int toPos = nodeLists.at(from).at(i);
        if (!isReached.at(toPos)) {
            searchPath(toPos, to);
        } 
    }
    if (!stop) pathStack.pop_back();
    return;
}

// これは深さ優先探索でできそう
int main() {
    cin >> N >> X >> Y;
    rep(i,0,N-1) {
        int U,V;
        cin >> U >> V;
        nodeLists.at(U).push_back(V);
        nodeLists.at(V).push_back(U);
    }
    searchPath(X, Y);
    for(int i=0; i<(int)pathStack.size(); i++) {
        cout << pathStack.at(i) << " ";
    }
    cout << endl;
}

Submission Info

Judge Result