木の列挙

[beet-aizu]

https://yukicoder.me/problems/no/1302 の愚直解を書くのに使った

TODO: ↓をまともにする

vector<vector<vector<int>>> trees;
vector<int> vs;
void dfs(int i,int n){
  if(i+2==n){
    vector<vector<int>> G(n);
    auto add_edge=[&](int x,int y){
      G[x].emplace_back(y);
      G[y].emplace_back(x);
    };
    auto mex=[&](vector<int> as){
      set<int> ss(as.begin(),as.end());
      int res=0;
      while(ss.count(res)) res++;
      return res;
    };
    auto as=vs;
    for(int i=0;i<n-2;i++){
      int b=mex(as);
      add_edge(as[i],b);
      as[i]=b;
    }
    int x=mex(as);
    as.emplace_back(x);
    int y=mex(as);
    add_edge(x,y);
    trees.emplace_back(G);
    return;
  }
  for(int v=0;v<n;v++){
    vs[i]=v;
    dfs(i+1,n);
  }
}

void enumerate_tree(int n){
  vs.resize(n-2);
  dfs(0,n);
}

[beet-aizu]

http://joisino.hatenablog.com/entry/2017/08/20/200000