Submission #1796890

---

Source Code Expand

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

using ll = long long;

template <typename T> T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> g(N);
    for(int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    vector<int> leaf;
    for(int i = 0; i < N; ++i) {
        if(g[i].size() == 1) {
            leaf.push_back(i);
        }
    }

    int s = leaf[0], t = leaf[1];
    vector<int> d(N, inf<int>);
    d[s] = 0;
    vector<int> prev(N, -1);
    queue<int> que;
    que.push(s);
    while(!que.empty()) {
        int v = que.front();
        que.pop();
        for(auto to : g[v]) {
            if(d[to] != inf<int>) {
                continue;
            }
            d[to] = d[v] + 1;
            que.push(to);
            prev[to] = v;
        }
    }
    vector<int> res;
    int now = t;
    while(now != -1) {
        res.push_back(now);
        now = prev[now];
    }
    cout << res.size() << endl;
    for(int i = 0; i < (int)res.size(); ++i) {
        cout << res[i] + 1 << " \n"[i + 1 == res.size()];
    }
}

Submission Info

Judge Result