| 108 | // 如果status == 1，表示u遍历到儿子v，然后发现dfn[v] != 0 |
| 109 | // 对应递归版for循环中的第二个分支 |
| 110 | public static void tarjan2(int node) { |
| 111 | stacksize = 0; |
| 112 | push(node, -1, -1); |
| 113 | int v; |
| 114 | while (stacksize > 0) { |
| 115 | pop(); |
| 116 | if (status == -1) { |
| 117 | dfn[u] = low[u] = ++cntd; |
| 118 | sta[++top] = u; |
| 119 | e = head[u]; |
| 120 | } else { |
| 121 | v = to[e]; |
| 122 | if (status == 0) { |
| 123 | low[u] = Math.min(low[u], low[v]); |
| 124 | } |
| 125 | if (status == 1 && belong[v] == 0) { |
| 126 | low[u] = Math.min(low[u], dfn[v]); |
| 127 | } |
| 128 | e = nxt[e]; |
| 129 | } |
| 130 | if (e != 0) { |
| 131 | v = to[e]; |
| 132 | if (dfn[v] == 0) { |
| 133 | // (当前节点, 状态, 边)先进入栈 |
| 134 | // (儿子节点, 状态, 边)再进入栈 |
| 135 | // 那么儿子节点的tarjan过程会先执行 |
| 136 | // 等到处理当前节点时，low[儿子节点]信息就生成好了 |
| 137 | push(u, 0, e); |
| 138 | push(v, -1, -1); |
| 139 | } else { |
| 140 | push(u, 1, e); |
| 141 | } |
| 142 | } else { |
| 143 | if (dfn[u] == low[u]) { |
| 144 | sccCnt++; |
| 145 | sccl[sccCnt] = idx + 1; |
| 146 | int pop; |
| 147 | do { |
| 148 | pop = sta[top--]; |
| 149 | belong[pop] = sccCnt; |
| 150 | sccArr[++idx] = pop; |
| 151 | } while (pop != u); |
| 152 | sccr[sccCnt] = idx; |
| 153 | } |
| 154 | } |
| 155 | } |
| 156 | } |
| 157 | |
| 158 | public static void main(String[] args) throws Exception { |
| 159 | FastReader in = new FastReader(System.in); |