| 106 | |
| 107 | // 迭代版 |
| 108 | public static void tarjan2(int node) { |
| 109 | stacksize = 0; |
| 110 | push(node, -1, 0, -1); |
| 111 | int v; |
| 112 | while (stacksize > 0) { |
| 113 | pop(); |
| 114 | if (status == -1) { |
| 115 | dfn[u] = low[u] = ++cntd; |
| 116 | sta[++top] = u; |
| 117 | e = head1[u]; |
| 118 | } else { |
| 119 | v = to1[e]; |
| 120 | if (status == 0) { |
| 121 | low[u] = Math.min(low[u], low[v]); |
| 122 | if (low[v] >= dfn[u]) { |
| 123 | cntn++; |
| 124 | addEdge2(cntn, u); |
| 125 | addEdge2(u, cntn); |
| 126 | int pop; |
| 127 | do { |
| 128 | pop = sta[top--]; |
| 129 | addEdge2(cntn, pop); |
| 130 | addEdge2(pop, cntn); |
| 131 | } while (pop != v); |
| 132 | } |
| 133 | } else { |
| 134 | low[u] = Math.min(low[u], dfn[v]); |
| 135 | } |
| 136 | e = next1[e]; |
| 137 | } |
| 138 | if (e != 0) { |
| 139 | v = to1[e]; |
| 140 | if (dfn[v] == 0) { |
| 141 | push(u, 0, 0, e); |
| 142 | push(v, -1, 0, -1); |
| 143 | } else { |
| 144 | push(u, 1, 0, e); |
| 145 | } |
| 146 | } |
| 147 | } |
| 148 | } |
| 149 | |
| 150 | // 递归版 |
| 151 | public static void dpOnTree1(int u, int fa) { |