提出 #68579462

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
constexpr ll MOD = 1e9+7; // 998244353

int N, M;
set<pair<int, int>> G[200005];

void addEdge(int u, int v, int w=1) {
    G[u].insert({v, w});
    G[v].insert({u, w});
}

void eraseEdge(int u, int v) {
    G[u].erase(G[u].lower_bound({v, 0}));
    G[v].erase(G[v].lower_bound({u, 0}));
}

void compress() {
    set<int> q;
    for (int u = 1; u <= N; ++u) q.insert(u);
    while (!q.empty()) {
        int u = *q.begin();
        q.erase(q.begin());
        if (u == 1 || u == N) continue;
        else if (G[u].size() == 1) {
            int v = G[u].begin()->first;
            eraseEdge(u, v);
            q.insert(v);
        } else if (G[u].size() == 2) {
            auto [v1, w1] = *G[u].begin();
            auto [v2, w2] = *(++G[u].begin());
            eraseEdge(u, v1);
            eraseEdge(u, v2);
            if (v1 != v2) {
                addEdge(v1, v2, w1+w2);
            } else {
                q.insert(v1);
                q.insert(v2);
            }
        }
    }
    // for (int u = 1; u <= N; ++u) {
    //     assert(u == 1 || u == N || G[u].size() == 0 || G[u].size() >= 3);
    // }
}

bool seen[200005];
int ans[200005];
void dfs(int u, int dep = 0) {
    if (u == N) {
        ans[dep]++;
        return;
    }
    seen[u] = true;
    for (auto [v, w] : G[u]) {
        if (!seen[v]) dfs(v, dep+w);
    }
    seen[u] = false;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> M;
    for (int u, v, i = 0; i < M; ++i) {
        cin >> u >> v;
        addEdge(u, v);
    }
    compress();
    dfs(1);
    for (int k = 1; k < N; ++k) cout << ans[k] << " ";
    cout << "\n";
}

提出情報

ジャッジ結果