| 160 | |
| 161 | // dfs1的迭代版 |
| 162 | public static void dfs3() { |
| 163 | stacksize = 0; |
| 164 | push(1, 0, -1); |
| 165 | while (stacksize > 0) { |
| 166 | pop(); |
| 167 | if (edge == -1) { |
| 168 | fa[first] = second; |
| 169 | dep[first] = dep[second] + 1; |
| 170 | siz[first] = 1; |
| 171 | edge = head[first]; |
| 172 | } else { |
| 173 | edge = next[edge]; |
| 174 | } |
| 175 | if (edge != 0) { |
| 176 | push(first, second, edge); |
| 177 | if (to[edge] != second) { |
| 178 | push(to[edge], first, -1); |
| 179 | } |
| 180 | } else { |
| 181 | for (int e = head[first], v; e > 0; e = next[e]) { |
| 182 | v = to[e]; |
| 183 | if (v != second) { |
| 184 | siz[first] += siz[v]; |
| 185 | if (son[first] == 0 || siz[son[first]] < siz[v]) { |
| 186 | son[first] = v; |
| 187 | } |
| 188 | } |
| 189 | } |
| 190 | } |
| 191 | } |
| 192 | } |
| 193 | |
| 194 | // dfs2的迭代版 |
| 195 | public static void dfs4() { |