Processing math: 100%
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Functional Graph

コードについての説明

Functional Graph とは各頂点の出次数がちょうど 1 の単純な有向グラフのことである. グラフが {1,,n}{1,,n} の関数として表現できることがその名の由来であると思われる.
定義よりグラフはループと(無向グラフと見たとき)ループ上の頂点を根とする木からなるグラフになる.

(関数)
solve(): ループ上の頂点を loop の配列に入れる.
make_graph(): (無向グラフと見たとき)ループ上の頂点を根とする木たちをループ側から端に向かう方向(元とは逆の方向)の有向森とみたグラフを構築する.

時間計算量: O(n)

コード

  1. // すべての頂点の出次数が 1 のグラフ
  2. // loop に辺に沿ったループ上の頂点が入る
  3. // visit[v] は頂点 v が i(0_indexed) 番目のループ上の頂点なら i+1 (≧ 1),
  4. // v がループ上になく, i 番目のループにたどり着く場合 -(i+1) (≦ -1) が格納される.
  5. // make_graph() でループから葉へ向かう方向の森を構築
  6.  
  7. class FunctionalGraph {
  8. private:
  9. const int V;
  10. int loop_id;
  11. vector<int> nx;
  12. void make_loop(const int st, int nw, vector<int>& vec){
  13. while(nx[nw] != st){
  14. vec.push_back(nx[nw]);
  15. visit[nx[nw]] = loop_id;
  16. nw = nx[nw];
  17. }
  18. }
  19. int dfs(int u, vector<int>& vec){
  20. visit[u] = -loop_id;
  21. int v = nx[u];
  22. if(visit[v] == -loop_id){
  23. vec.push_back(u), vec.push_back(v);
  24. visit[u] = visit[v] = loop_id;
  25. make_loop(u, v, vec);
  26. loop_id++;
  27. return 0;
  28. }else if(visit[v] == 0){
  29. const int res = dfs(v, vec);
  30. if(res == 0) return 0;
  31. else return visit[u] = res;
  32. }
  33. return visit[u] = (visit[v] > 0 ? -visit[v] : visit[v]);
  34. }
  35. void make_graph(){
  36. graph.resize(V);
  37. for(int i = 0; i < V; i++){
  38. if(visit[i] < 0) graph[nx[i]].push_back(i);
  39. }
  40. }
  41.  
  42. public:
  43. vector<int> visit;
  44. vector<vector<int> > loop, graph;
  45. FunctionalGraph(const int node_size)
  46. : V(node_size), loop_id(1), nx(V, 0), visit(V, 0){}
  47. void add_edge(int u, int v){
  48. nx[u] = v;
  49. if(u == nx[u]) visit[u] = loop_id++, loop.push_back({u});
  50. }
  51. void solve(){
  52. for(int i = 0; i < V; i++){
  53. if(visit[i] == 0){
  54. vector<int> vec;
  55. dfs(i, vec);
  56. if(!vec.empty()) loop.push_back(move(vec));
  57. }
  58. }
  59. // make_graph();
  60. }
  61. };

verify 用の問題

JOI : 報告(report) 提出コード