| 92 | } |
| 93 | |
| 94 | public static void tarjan(int u) { |
| 95 | dfn[u] = low[u] = ++cntd; |
| 96 | sta[++cnts] = u; |
| 97 | for (int e = head1[u]; e > 0; e = next1[e]) { |
| 98 | int v = to1[e]; |
| 99 | if (dfn[v] == 0) { |
| 100 | tarjan(v); |
| 101 | low[u] = Math.min(low[u], low[v]); |
| 102 | if (low[v] >= dfn[u]) { |
| 103 | cntn++; |
| 104 | addEdge2(cntn, u); |
| 105 | addEdge2(u, cntn); |
| 106 | int pop; |
| 107 | do { |
| 108 | pop = sta[cnts--]; |
| 109 | addEdge2(cntn, pop); |
| 110 | addEdge2(pop, cntn); |
| 111 | } while (pop != v); |
| 112 | } |
| 113 | } else { |
| 114 | low[u] = Math.min(low[u], dfn[v]); |
| 115 | } |
| 116 | } |
| 117 | } |
| 118 | |
| 119 | public static void dfs1(int u, int f) { |
| 120 | fa[u] = f; |