#1150508 (C++23) No.3463 Beltway

• 問題: No.3463 Beltway
• ユーザー: karinohito
• 提出日時: 2026-02-28 15:31:24
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 306 ms / 2,000 ms
• コード長: 3,855 bytes
• コンパイル時間: 3,868 ms
• コンパイル使用メモリ: 366,628 KB
• 実行使用メモリ: 74,832 KB
• 最終ジャッジ日時: 2026-02-28 15:53:36
• 合計ジャッジ時間: 7,509 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 1
other	AC * 17

ソースコード

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

using vi=vector<int>;
using vvi=vector<vi>;
#define rep(i,n) for(int i=0;i<n;i++)

struct LowLink {
  int n;
  vi used, ord, low, low2, art, tps, par, comp;
  vvi g;
  vector<pair<int, int>> bridge, tmp;
  vector<vector<pair<int, int>>> bc; // Biconnected Components に必要

  LowLink(int n, vvi &g)
      : n(n), g(g), used(n, 0), ord(n), low(n), tps(n), par(n) {
    int k = 0;
    rep(i, n) if(used[i] == 0) k = dfs(i, -1, k);
    low2 = low;

    // 多重辺があるとき
    rep(i, n) {
      int v = tps[n - 1 - i];
      bool flag = false;
      for(auto u : g[v]) {
        if(u == par[v] && !flag) {
          flag = true;
          continue;
        }
        if(low2[v] > low2[u]) low2[v] = low2[u];
      }
    }
  };

  int dfs(int v, int p, int k) {
    used[v] = 1;
    tps[k] = v;
    ord[v] = k++;
    low[v] = ord[v];
    par[v] = p;
    bool flag = false;
    int c = 0;
    for(auto u : g[v]) {
      if(used[u] == 0) {
        c++;
        k = dfs(u, v, k);
        low[v] = min(low[v], low[u]);
        flag |= (p != -1) && (low[u] >= ord[v]);
        if(ord[v] < low[u]) bridge.push_back({v, u});
      }
      else if(u != p) low[v] = min(low[v], ord[u]);
    }
    flag |= (p == -1 && c > 1);
    if(flag) art.push_back(v);
    return k;
  };

  vvi TwoEdgeCC() {
    comp.assign(n, -1);
    int k = 0;
    rep(i, n) if(comp[i] == -1) dfs2(i, -1, k);
    vvi grp(k);
    rep(i, n) grp[comp[i]].push_back(i);
    return grp;
  }

  // Two-Edge-Connected Components に必要
  void dfs2(int v, int p, int &k) {
    if(p >= 0 && ord[p] >= low2[v]) comp[v] = comp[p];
    else comp[v] = k++;
    for(auto u : g[v]) {
      if(comp[u] == -1) dfs2(u, v, k);
    }
  }

  vector<vector<pair<int, int>>> BiCC() {
    used.assign(n, 0);
    rep(i, n) if(!used[i]) dfs3(i, -1);
    return bc;
  }

  // Biconnected Components に必要
  void dfs3(int v, int p) {
    used[v] = 1;
    for(auto u : g[v]) {
      if(u == p) continue;
      if(!used[u] || ord[u] < ord[v]) tmp.push_back(minmax(u, v));
      if(!used[u]) {
        dfs3(u, v);
        if(low[u] >= ord[v]) {
          bc.emplace_back();
          while(true) {
            auto e = tmp.back();
            tmp.pop_back();
            bc.back().push_back(e);
            if(e.first == min(u, v) && e.second == max(u, v)) break;
          }
        }
      }
    }
  }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N,M,S,T;
    cin>>N>>M>>S>>T;
    S--;T--;
    vector<vector<int>> G(N);
    vector<ll> C(N,0);
    set<array<ll,2>> EF;
    for(ll i=0;i<M;i++){
        ll u,v;
        cin>>u>>v;
        u--;v--;
        if(u>v)swap(u,v);
        G[u].push_back(v);
        G[v].push_back(u);
        EF.insert({u,v});
        C[u]++;
        C[v]++;
    } 
    LowLink LL(N,G);
    for(auto [u,v]:LL.bridge){
        EF.erase({min(u,v),max(u,v)});
    }
    queue<ll> Q;
    for(ll i=0;i<N;i++){
        if(C[i]==1)Q.push(i);
    }
    while(!Q.empty()){
        ll p=Q.front();
        Q.pop();
        for(ll v:G[p]){
            
            C[v]--;
            if(C[v]==1)Q.push(v);
        }
    }
    const ll INF=1e18;
    vector<ll> D(N,INF);
    vector<ll> R(N,-1);
    D[S]=0;
    queue<ll> que; 
    que.push(S);
    
    vector<bool> seen(N,0);
    while(!que.empty()){
        ll n=que.front();
        que.pop();
        if(seen[n])continue;
        seen[n]=1;
        for(auto v:G[n]){
            if(seen[v])continue;
            if(D[v]<=D[n]+1)continue;
            D[v]=D[n]+1;
            R[v]=n;
            que.push(v);
        }
    }
    if(D[T]>1e17)cout<<-1<<"\n";
    else{
        ll an=0;
        while(T!=S){
            ll Y=R[T];
            if(EF.count({min(Y,T),max(Y,T)}))an++;
            T=Y;
        }
        cout<<an<<"\n";
    }
}