1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| vector<int> edge[maxn], st; int n, id, dfn[maxn], low[maxn], vis[maxn]; int cnt, bel[maxn], ind[maxn], oud[maxn];
void dfs(int u){ dfn[u] = low[u] = ++id; vis[u] = 1; st.push_back(u); for (int i = 0; i < edge[u].size(); i++){ int v = edge[u][i]; if (!dfn[v]){ dfs(v); low[u] = min(low[u], low[v]); } else if (vis[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]){ cnt++; int t = 0; do{ t = st.back(); st.pop_back(); bel[t] = cnt; vis[t] = 0; } while(t != u); } }
void init(){ ms(dfn, 0); ms(vis, 0); st.clear(); cnt = id = 0; }
|