codeforces/dominators_tree.cpp at master · Mateuszrze/codeforces · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

/*
na DAGU przeszlo jedno zadanie
na zwyklym grafie nie wiem ale raczej dziala
wziete z biblioteczki Radka Serafina
numeruje sie od zera, korzen to 0
doit zwraca wektor ojcow w drzewie dominatorow (-1 oznacza ze wierzcholek jest korzeniem)
*/
struct Dominators{
  int n_orig, n;
  vector < int > parent, semi, vertex, dom, ancestor, label;
  vector< vector < int > > succ, pred, bucket;

  Dominators(int _n):n_orig(_n), n(2 * (_n + 1)), parent(n), semi(n), vertex(n), dom(n), ancestor(n), label(n), succ(n), pred(n), bucket(n) {
    n = n_orig;
  }

  void add_edge(int a,int b){
    a++;b++;
    dbg(a, b);
    succ[a].pb(b);
  }

  void COMPRESS(int v) {
    if(ancestor[ancestor[v]] != 0) {
      COMPRESS(ancestor[v]);
      if(semi[label[ancestor[v]]] < semi[label[v]]) {
        label[v] = label[ancestor[v]];
      }
      ancestor[v]=ancestor[ancestor[v]];
    }
  }

  void LINK(int v, int w) {
    ancestor[w]=v;
  }

  int EVAL(int v) {
    if(ancestor[v] == 0)
      return v;
    else {
      COMPRESS(v);
      return label[v];
    }
  }

  void DFS(int v) {
    semi[v] = ++n;
    vertex[n] = v;
    for(auto ng : succ[v]) {
      if(semi[ng] == 0) {
        parent[ng]=v;
        DFS(ng);
      }
      pred[ng].push_back(v);
    }
  }

  vector<int> doit() {
    iota(all(label), 0);
    DFS(1);
    for(int i=n; i>=2; --i) {
      int w = vertex[i];
      for(auto ng : pred[w]) {
        int u = EVAL(ng);
        if(semi[u] < semi[w])
          semi[w] = semi[u];
      }
      bucket[vertex[semi[w]]].push_back(w);
      LINK(parent[w],w);
      while(!bucket[parent[w]].empty()) {
        int v = bucket[parent[w]].back();
        bucket[parent[w]].pop_back();
        int u = EVAL(v);
        if(semi[u] < semi[v])
          dom[v] = u;
        else
          dom[v] = parent[w];
      }
    }

    //step 4
    for(int i=2; i<=n; ++i) {
      int w = vertex[i];
      if(dom[w] != vertex[semi[w]])
        dom[w] = dom[dom[w]];
    }
    dom[1]=0;
    vector<int> res(n_orig);
    for(int i = 0;i < n_orig;i++)
      res[i] = dom[i + 1] - 1;
    return res;
  }
};