| 56 | } |
| 57 | |
| 58 | public static void tarjan(int u, int preEdge) { |
| 59 | dfn[u] = low[u] = ++cntd; |
| 60 | sta[++top] = u; |
| 61 | for (int e = head[u]; e > 0; e = nxt[e]) { |
| 62 | if ((e ^ 1) == preEdge) { |
| 63 | continue; |
| 64 | } |
| 65 | int v = to[e]; |
| 66 | if (dfn[v] == 0) { |
| 67 | tarjan(v, e); |
| 68 | low[u] = Math.min(low[u], low[v]); |
| 69 | } else { |
| 70 | low[u] = Math.min(low[u], dfn[v]); |
| 71 | } |
| 72 | } |
| 73 | if (dfn[u] == low[u]) { |
| 74 | ebccCnt++; |
| 75 | int pop; |
| 76 | do { |
| 77 | pop = sta[top--]; |
| 78 | belong[pop] = ebccCnt; |
| 79 | } while (pop != u); |
| 80 | } |
| 81 | } |
| 82 | |
| 83 | public static void condense() { |
| 84 | cntg = 0; |