Linear solution of ICPC WF 2015 K problem

readme.txt

＊ICPC WF 2015 K(https://icpc.kattis.com/problems/tours) の解法について

「必ず同時にサイクルに含まれる辺のグループ」に分解し、そのサイズのGCDの約数を列挙すれば解ける。（この部分の証明は本題ではないので、最後に回します。）

＊「必ず同時にサイクルに含まれる辺のグループ」に分解するアルゴリズム

・二乗解法
ある橋でない辺eを取り除いたときに、新たに橋になるものが辺eと同じグループ

・hash解法
DFS木を作って、後退辺に乱数を割り当てる。
後退辺を区間だとみなして、区間内の辺に後退辺に割り当てられた乱数値を足す。
同じ値を持った辺どうしが同じグループになる。
橋の値は0になる。

・線形解法
基本アイデアはhashのと同じ。
まずはpathの場合で考えてみる。
辺は「辺を覆う区間（後退辺）の数（nestと呼ぶ）」「辺を覆う区間のうち、始点（葉に近い方）が最も根に近い物（Innermost intervalと呼ぶ）」の組でグループ分けできる。
実際に計算するには、
- 区間の始点が来たらnest++
- 区間の終点が来たらnest--
- 「今後Innermost intervalになる可能性のある区間」をスタックで管理する。
スタックの管理は具体的には、区間をpushするときにはまず終点がその区間よりも根から遠い区間をpopしてからpushする。

pathならわりとどうとでもなるんですが、木の場合に、スタックのマージをどうするかとかがポイントです。
２つの部分木から来たデータをマージするときは、今見ている頂点をvとして、
- スタックの末尾の区間（最も長い区間）の終点どうしを比較して、根に近い方をs、もう一方をtとする。
- tに含まれる区間は全て、始点がvであったとみなしても良い。なぜなら、sの最長の区間に覆われている以上、tの方の部分木内にある「覆われてる区間の集合」はそれ以降現れないから。
- tに含まれている区間の始点がvで揃ったということは、tに含まれる最も長い区間だけをスタックに残せばいいことになる。
- sに「tのうち最も長い区間」を、普通の区間をpushするときと同様に追加する。
これで、DFS木に含まれる辺のグループ分けはできる。

残るは、後退辺についての計算で、
nest=1のときだけ、辺eと辺eを覆う後退辺が同じグループになる。

ちなみに、nest=0のときは橋になる。

----

＊「必ず同時にサイクルに含まれる辺のグループ」に分解すれば解けることの証明（りんごさんに聞いた物を自分なりにまとめてみました）

「必ず同時にサイクルに含まれる辺のグループ」に分ける。
任意のグループAに対して、AXからなるサイクルとAYからなるサイクルがあるような、異なるグループの集合X,Yが必ず存在する。（そうでないならAとXは同じグループのはず）
k色で塗るとき、ある色に注目して、A,X,Yに含まれるその色の個数をa,x,yとすると、
- a+x = (|A|+|X|)/k
- a+y = (|A|+|Y|)/k
- x+y = (|X|+|Y|)/k
が成り立ち、a=|A|/kとなる。よって、kは|A|の約数でなければならない。
全てのグループの長さがkの倍数なら、それぞれのグループ内の色が均等になるようにすれば、どうサイクルをとっても行ける。
よって、kが|A|の約数になっていることが必要十分条件

＊おまけ

「必ず同時にサイクルに含まれる辺のグループへの分解」にいい感じの名前をつけてください。（もし既に名前が付いていれば教えて下さい。）

ICPC_WF2015_K_hash.cpp

// 乱数依存＋map使用の軽実装バージョン
#include <cstdio>
#include <vector>
#include <map>
#include <cstdlib>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
typedef long long ll;

class ToursDecomposition {
 public:
  struct Edge {
    int u, v;
    Edge() {}
    Edge(int u, int v) : u(u), v(v) {}
  };
  int n;
  vector< vector<int> > to;
  vector<int> depth;
  vector<ll> hash;
  map< ll, vector<Edge> > group;
  ToursDecomposition() {}
  ToursDecomposition(int n) : n(n), to(n), depth(n, -1), hash(n) {}
  void AddEdge(int u, int v) {
    to[u].push_back(v);
    to[v].push_back(u);
  }
  void Init() {
    rep(i,n) {
      if (depth[i] != -1) continue;
      depth[i] = 0;
      dfs(i, -1);
    }
  }
 private:
  void dfs(int v, int p) {
    for (int u : to[v]) {
      if (depth[u] == -1) {
        depth[u] = depth[v] + 1;
        dfs(u, v);
        hash[v] += hash[u];
        group[hash[u]].push_back(Edge(u, v));
      } else if (depth[u] < depth[v] && u != p) {
        ll r = rand();
        group[r].push_back(Edge(u, v));
        hash[v] += r;
        hash[u] -= r;
      }
    }
  }
};

int gcd(int x, int y) {
  return y ? gcd(y, x%y) : x;
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  ToursDecomposition td(n);
  rep(i,m) {
    int u, v;
    scanf("%d%d", &u, &v);
    td.AddEdge(u-1, v-1);
  }
  td.Init();
  int x = 0;
  for (auto g : td.group) {
    // printf("hash : %lld\n", g.first);
    // for (auto e : g.second) { printf("%d - %d\n", e.u+1, e.v+1);}
    if (g.first == 0) continue;
    x = gcd(x, g.second.size());
  }
  vector<int> ans;
  for (int i = 1; i <= x; ++i) {
    if (x%i == 0) ans.push_back(i);
  }
  rep(i,ans.size()) {
    if (i) printf(" ");
    printf("%d", ans[i]);
  }
  puts("");
  return 0;
}

ICPC_WF2015_K_linear.cpp

// 線形解法
#include <cstdio>
#include <vector>
#include <map>
#include <cstdlib>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;

class ToursDecomposition {
public:
  struct Edge {
    int u, v;
    Edge() {}
    Edge(int u, int v) : u(u), v(v) {}
  };
  int n;
  vector< vector<int> > to;
  vector<int> depth;
  vector< vector<Edge> > group;
  ToursDecomposition() {}
  ToursDecomposition(int n) : n(n), to(n), depth(n, -1), group(1) {}
  void AddEdge(int u, int v) {
    to[u].push_back(v);
    to[v].push_back(u);
  }
  void Init() {
    dat.resize(n, {Dat(-1, 0, -1)});
    rep(i,n) {
      if (depth[i] != -1) continue;
      depth[i] = 0;
      dfs(i, -1);
    }
  }
private:
  struct Dat {
    int v, nest, g;
    Dat() {}
    Dat(int v, int nest, int g) : v(v), nest(nest), g(g) {}
  };
  vector< vector<Dat> > dat;
  inline void add(vector<Dat>* s, int v) {
    int nest = s->back().nest;
    while (s->size() > 1) {
      if (depth[s->back().v] < depth[v]) break;
      s->pop_back();
    }
    s->push_back(Dat(v, nest+1, -1));
  }
  vector<Dat>* dfs(int v, int p) {
    vector<Dat>* s = &dat[v];
    for (int u : to[v]) {
      if (depth[u] == -1) {
        depth[u] = depth[v] + 1;
        vector<Dat>* t = dfs(u, v);
        int sv = (s->size() == 1 ? -1 : s->at(1).v);
        int tv = (t->size() == 1 ? -1 : t->at(1).v);
        if (sv == -1) {
          s = t;
        } else if (tv != -1) {
          if (depth[sv] > depth[tv]) {
            swap(s, t);
            swap(sv, tv);
          }
          add(s, tv);
          s->back().nest += t->back().nest-1;
        }
      } else if (u != p) {
        if (depth[u] < depth[v]) {
          add(s, u);
          if (s->size() == 2) s->begin()->g = group.size();
          group.push_back({Edge(u, v)});
        } else {
          s->back().nest--;
          s->back().g = -1;
        }
      }
    }
    if (s->back().v == v) {
      int nest = s->back().nest;
      s->pop_back();
      if (s->back().nest != nest) {
        s->back().g = -1;
      }
      s->back().nest = nest;
    }
    if (p == -1) return s;
    int g = (s->size() == 1 ? 0 : s->back().g);
    if (s->size() == 2 && s->back().nest == 1) g = s->begin()->g;
    if (g == -1) {
      s->back().g = group.size();
      group.push_back({Edge(p, v)});
    } else group[g].push_back(Edge(p, v));
    return s;
  }
};

int gcd(int x, int y) {
  return y ? gcd(y, x%y) : x;
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  ToursDecomposition td(n);
  rep(i,m) {
    int u, v;
    scanf("%d%d", &u, &v);
    td.AddEdge(u-1, v-1);
  }
  td.Init();
  int x = 0;
  for (int i = 1; i < td.group.size(); ++i) {
    x = gcd(x, td.group[i].size());
  }
  /*
  for (int i = 0; i < td.group.size(); ++i) {
    fprintf(stderr, "size : %d\n", (int)td.group[i].size());
    for (auto e : td.group[i]) fprintf(stderr, "%d %d\n", e.u+1, e.v+1);
  }//*/
  vector<int> ans;
  for (int i = 1; i <= x; ++i) {
    if (x%i == 0) ans.push_back(i);
  }
  rep(i,ans.size()) {
    if (i) printf(" ");
    printf("%d", ans[i]);
  }
  puts("");
  return 0;
}