ACPC 2021 Day2 J を一般グラフで解く (実装編)

Nachia さんの考えたアルゴリズムを実装しました。 www.mathenachia.blog

注意

• 簡単なランダムチェッカーを通しています。
• 時間計算量については確認していませんが、ACPC 2021 Day2 J を AC することはできました。
• 下のコードはグラフが入力された場合に答えるコードです。ACPC 2021 Day2 J を AC できるコードは大部分が同じなので掲載しません。以下のリンクから確認してください。 judge.u-aizu.ac.jp

#include <bits/stdc++.h>
using namespace std;
struct extended_block_cut_tree{
  int N, cnt;
  vector<vector<int>> G;
  extended_block_cut_tree(vector<vector<int>> &E){
    N = E.size();
    vector<int> next(N, -1);
    vector<int> d(N, -1);
    vector<int> imos(N, 0);
    for (int i = 0; i < N; i++){
      if (d[i] == -1){
        d[i] = 0;
        dfs1(E, next, d, imos, i);
      }
    }
    cnt = 0;
    G.resize(N + 1);
    vector<bool> used(N, false);
    for (int i = 0; i < N; i++){
      if (d[i] == 0){
        dfs2(E, d, imos, used, cnt, i);
      }
      if (E[i].empty()){
        G[i].push_back(N + cnt);
        G[N + cnt].push_back(i);
        cnt++;
        G.push_back({});
      }
    }
    G.pop_back();
  }
  void dfs1(vector<vector<int>> &E, vector<int> &next, vector<int> &d, vector<int> &imos, int v){
    for (int w : E[v]){
      if (d[w] == -1){
        d[w] = d[v] + 1;
        next[v] = w;
        dfs1(E, next, d, imos, w);
        imos[v] += imos[w];
      } else if (d[w] < d[v] - 1){
        imos[v]++;
        imos[next[w]]--;
      }
    }
  }
  void dfs2(vector<vector<int>> &E, vector<int> &d, vector<int> &imos, vector<bool> &used, int b, int v){
    used[v] = true;
    bool ok = false;
    for (int w : E[v]){
      if (d[w] == d[v] + 1 && !used[w]){
        if (imos[w] > 0){
          if (!ok){
            ok = true;
            G[v].push_back(N + b);
            G[N + b].push_back(v);
          }
          dfs2(E, d, imos, used, b, w);
        } else {
          G[v].push_back(N + cnt);
          G[N + cnt].push_back(v);
          cnt++;
          G.push_back({});
          dfs2(E, d, imos, used, cnt - 1, w);
        }
      }
    }
    if (!ok && d[v] > 0){
      G[v].push_back(N + b);
      G[N + b].push_back(v);
    }
  }
  int size(){
    return G.size();
  }
  vector<int> &operator [](int v){
    return G[v];
  }
};
struct ford_fulkerson{
  struct edge{
    int to, rev, cap;
    edge(int to, int rev, int cap): to(to), rev(rev), cap(cap){
    }
  };
  int N;
  vector<vector<edge>> G;
  ford_fulkerson(int N): N(N), G(N){
  }
  void add_edge(int from, int to){
    G[from].push_back(edge(to, G[to].size(), 1));
    G[to].push_back(edge(from, G[from].size() - 1, 0));
  }
  void max_flow(int s, int t, int F){
    int flow = 0;
    while (flow < F){
      vector<int> pv(N, -1);
      vector<int> pe(N, -1);
      vector<bool> used(N, false);
      used[s] = true;
      queue<int> Q;
      Q.push(s);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        int cnt = G[v].size();
        for (int i = 0; i < cnt; i++){
          int w = G[v][i].to;
          if (!used[w] && G[v][i].cap > 0){
            used[w] = true;
            pv[w] = v;
            pe[w] = i;
            Q.push(w);
          }
        }
      }
      if (!used[t]){
        break;
      }
      for (int v = t; v != s; v = pv[v]){
        G[pv[v]][pe[v]].cap--;
        G[v][G[pv[v]][pe[v]].rev].cap++;
      }
      flow++;
    }
  }
};
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  extended_block_cut_tree T(E);
  int V = T.size();
  vector<int> p(V, -1);
  vector<int> d(V, 0);
  for (int i = 0; i < V; i++){
    if (p[i] == -1){
      queue<int> Q;
      Q.push(i);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        for (int w : T[v]){
          if (w != p[v]){
            p[w] = v;
            d[w] = d[v] + 1;
            Q.push(w);
          }
        }
      }
    }
  }
  vector<int> bp = {N - 1};
  bool ok = false;
  while (true){
    int v = bp.back();
    if (v == 0){
      ok = true;
      break;
    }
    if (d[v] == 0){
      break;
    }
    bp.push_back(p[v]);
  }
  vector<int> ans(N, 0);
  if (!ok){
    for (int i = 1; i < N - 1; i++){
      ans[i] = N - 3;
    }
  } else {
    int L = bp.size();
    vector<bool> is_art(N, false);
    int art_cnt = 0;
    for (int i = 0; i < L; i++){
      if (1 <= bp[i] && bp[i] < N - 1 && T[bp[i]].size() >= 2){
        is_art[bp[i]] = true;
        art_cnt++;
      }
    }
    vector<vector<pair<int, int>>> edge(V - N);
    for (int i = 0; i < N; i++){
      for (int j : E[i]){
        if (i < j){
          int v;
          if (d[i] >= d[j]){
            v = p[i];
          } else {
            v = p[j];
          }
          edge[v - N].push_back(make_pair(i, j));
        }
      }
    }
    vector<int> id(N);
    for (int i = 1; i < L; i += 2){
      int cnt = 0;
      vector<int> id2;
      for (int j : T[bp[i]]){
        id[j] = cnt;
        id2.push_back(j);
        cnt++;
      }
      if (cnt == 2){
        continue;
      }
      vector<vector<int>> E2(cnt);
      for (pair<int, int> P : edge[bp[i] - N]){
        int u = id[P.first];
        int v = id[P.second];
        E2[u].push_back(v);
        E2[v].push_back(u);
      }
      int s = id[bp[i - 1]];
      int t = id[bp[i + 1]];
      ford_fulkerson G(cnt * 2);
      for (int j = 0; j < cnt; j++){
        G.add_edge(j, cnt + j);
      }
      for (int j = 0; j < cnt; j++){
        for (int k : E2[j]){
          G.add_edge(cnt + j, k);
        }
      }
      G.max_flow(cnt + s, t, 2);
      vector<vector<int>> path;
      for (ford_fulkerson::edge e : G.G[t]){
        if (e.cap > 0 && e.to != cnt + t){
          vector<int> tmp = {t};
          int v = e.to;
          while (v != cnt + s){
            if (v < cnt){
              tmp.push_back(v);
            }
            for (ford_fulkerson::edge e : G.G[v]){
              if (e.cap > 0){
                v = e.to;
                break;
              }
            }
          }
          tmp.push_back(s);
          path.push_back(tmp);
        }
      }
      reverse(path[0].begin(), path[0].end());
      reverse(path[1].begin(), path[1].end());
      for (int j = 0; j < 2; j++){
        int cnt1 = path[1].size();
        vector<bool> is_path1(cnt, false);
        for (int k = 1; k < cnt1 - 1; k++){
          is_path1[path[1][k]] = true;
        }
        vector<vector<int>> E3(cnt);
        for (int u = 0; u < cnt; u++){
          for (int v : E2[u]){
            if (!is_path1[u] && !is_path1[v]){
              E3[u].push_back(v);
            }
          }
        }
        extended_block_cut_tree T2(E3);
        int V2 = T2.size();
        vector<int> p2(V2, -1);
        queue<int> Q2;
        Q2.push(s);
        while (!Q2.empty()){
          int v = Q2.front();
          Q2.pop();
          for (int w : T2[v]){
            if (w != p2[v]){
              p2[w] = v;
              Q2.push(w);
            }
          }
        }
        vector<int> path2;
        path2.push_back(t);
        for (int v = p2[t]; v != s; v = p2[v]){
          if (v < cnt && T2[v].size() >= 2){
            path2.push_back(v);
          }
        }
        path2.push_back(s);
        reverse(path2.begin(), path2.end());
        path[0] = path2;
        int cnt0 = path[0].size();
        for (int k = 0; k < cnt0 - 1; k++){
          int u = path[0][k];
          int v = path[0][k + 1];
          bool ee = false;
          for (int w : E2[u]){
            if (w == v){
              ee = true;
            }
          }
          if (!ee){
            E2[u].push_back(v);
            E2[v].push_back(u);
          }
        }
        vector<bool> gray(cnt, true);
        for (int k = 0; k < cnt0; k++){
          gray[path[0][k]] = false;
        }
        for (int k = 0; k < cnt1; k++){
          gray[path[1][k]] = false;
        }
        vector<bool> re(cnt, false);
        vector<bool> used2(cnt, false);
        for (int k = 0; k < cnt; k++){
          if (gray[k] && !used2[k]){
            used2[k] = true;
            bool blue = false;
            queue<int> Q;
            Q.push(k);
            vector<int> cc;
            while (!Q.empty()){
              int v = Q.front();
              Q.pop();
              cc.push_back(v);
              for (int w : E2[v]){
                if (gray[w] && !used2[w]){
                  used2[w] = true;
                  Q.push(w);
                } else if (is_path1[w]){
                  blue = true;
                }
              }
            }
            if (!blue){
              for (int v : cc){
                re[v] = true;
              }
            }
          }
        }
        for (int k = 0; k < cnt; k++){
          if (re[k]){
            E2[k].clear();
          } else {
            vector<int> tmp;
            for (int v : E2[k]){
              if (!re[v]){
                tmp.push_back(v);
              }
            }
            E2[k] = tmp;
          }
        }
        swap(path[0], path[1]);
      }
      vector<int> type(cnt, -1);
      for (int v : path[0]){
        type[v] = 0;
      }
      for (int v : path[1]){
        type[v] = 1;
      }
      type[s] = 2;
      type[t] = 2;
      int cnt0 = path[0].size();
      vector<int> pos0(cnt, -1);
      for (int j = 0; j < cnt0; j++){
        pos0[path[0][j]] = j;
      }
      int cnt1 = path[1].size();
      vector<int> pos1(cnt, -1);
      for (int j = 0; j < cnt1; j++){
        pos1[path[1][j]] = j;
      }
      vector<pair<int, int>> E3;
      vector<bool> used(cnt, false);
      for (int j = 0; j < cnt; j++){
        if (!used[j] && type[j] == -1){
          used[j] = true;
          vector<int> id;
          vector<int> p0, p1;
          queue<int> Q;
          Q.push(j);
          while (!Q.empty()){
            int v = Q.front();
            Q.pop();
            id.push_back(v);
            for (int w : E2[v]){
              if (!used[w] && type[w] == -1){
                used[w] = true;
                Q.push(w);
              } else if (type[w] == 0){
                p0.push_back(w);
              } else if (type[w] == 1){
                p1.push_back(w);
              } else if (type[w] == 2){
                p0.push_back(w);
                p1.push_back(w);
              }
            }
          }
          for (int v : p0){
            for (int w : p1){
              E3.push_back(make_pair(pos0[v], pos1[w]));
            }
          }
        }
      }
      vector<int> mx1(cnt0, cnt1 - 2);
      vector<int> mn1(cnt0, 1);
      vector<int> mx2(cnt1, cnt0 - 2);
      vector<int> mn2(cnt1, 1);
      for (pair<int, int> P : E3){
        int u = P.first;
        int v = P.second;
        if (u > 0){
          mx1[u - 1] = min(mx1[u - 1], v);
        }
        if (u < cnt0 - 1){
          mn1[u + 1] = max(mn1[u + 1], v);
        }
        if (v > 0){
          mx2[v - 1] = min(mx2[v - 1], u);
        }
        if (v < cnt1 - 1){
          mn2[v + 1] = max(mn2[v + 1], u);
        }
      }
      for (int j = cnt0 - 2; j >= 0; j--){
        mx1[j] = min(mx1[j], mx1[j + 1]);
      }
      for (int j = 0; j < cnt0 - 1; j++){
        mn1[j + 1] = max(mn1[j + 1], mn1[j]);
      }
      for (int j = cnt1 - 2; j >= 0; j--){
        mx2[j] = min(mx2[j], mx2[j + 1]);
      }
      for (int j = 0; j < cnt1 - 1; j++){
        mn2[j + 1] = max(mn2[j + 1], mn2[j]);
      }
      for (int j = 1; j < cnt0 - 1; j++){
        ans[id2[path[0][j]]] += max(0, mx1[j] - mn1[j] + 1);
      }
      for (int j = 1; j < cnt1 - 1; j++){
        ans[id2[path[1][j]]] += max(0, mx2[j] - mn2[j] + 1);
      }
    }
    for (int i = 1; i < N - 1; i++){
      ans[i] += art_cnt;
      if (is_art[i]){
        ans[i] = N - 3;
      }
    }
  }
  for (int i = 1; i < N - 1; i++){
    cout << ans[i];
    if (i < N - 2){
      cout << ' ';
    }
  }
  cout << endl;
}