| 115 | |
| 116 | // dfs1的迭代版 |
| 117 | public static void dfs3() { |
| 118 | stacksize = 0; |
| 119 | push(root, 0, -1); |
| 120 | while (stacksize > 0) { |
| 121 | pop(); |
| 122 | if (edge == -1) { |
| 123 | fa[first] = second; |
| 124 | dep[first] = dep[second] + 1; |
| 125 | siz[first] = 1; |
| 126 | edge = head[first]; |
| 127 | } else { |
| 128 | edge = next[edge]; |
| 129 | } |
| 130 | if (edge != 0) { |
| 131 | push(first, second, edge); |
| 132 | if (to[edge] != second) { |
| 133 | push(to[edge], first, -1); |
| 134 | } |
| 135 | } else { |
| 136 | for (int e = head[first], v; e > 0; e = next[e]) { |
| 137 | v = to[e]; |
| 138 | if (v != second) { |
| 139 | siz[first] += siz[v]; |
| 140 | if (son[first] == 0 || siz[son[first]] < siz[v]) { |
| 141 | son[first] = v; |
| 142 | } |
| 143 | } |
| 144 | } |
| 145 | } |
| 146 | } |
| 147 | } |
| 148 | |
| 149 | // dfs2的迭代版 |
| 150 | public static void dfs4() { |