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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| #include <algorithm> #include <cstdio> #include <numeric> using namespace std;
const int N = 100000, M = 500000; struct Arc { int v, next; } pool[2*M], *pit; int e[N], ee[N], tick, dfn[N], rdfn[N], uf[N], sdom[N], best[N], idom[N];
void dfs(int u) { dfn[u] = tick; rdfn[tick++] = u; for (int v, a = e[u]; ~a; a = pool[a].next) if (dfn[v = pool[a].v] < 0) { uf[v] = u; dfs(v); } }
int eval(int v, int cur) { if (dfn[v] <= cur) return v; int u = uf[v], r = eval(u, cur); if (dfn[best[u]] < dfn[best[v]]) best[v] = best[u]; return uf[v] = r; }
void semiNca(int n, int r) { fill_n(idom, n, -1); fill_n(dfn, n, -1); tick = 0; dfs(r); iota(best, best+n, 0); for (int i = tick; --i; ) { int v = rdfn[i], u; sdom[v] = v; for (int a = ee[v]; ~a; a = pool[a].next) if (~dfn[u = pool[a].v]) { eval(u, i); if (dfn[best[u]] < dfn[sdom[v]]) sdom[v] = best[u]; } best[v] = sdom[v]; idom[v] = uf[v]; } for (int i = 1; i < tick; i++) { int v = rdfn[i]; while (dfn[idom[v]] > dfn[sdom[v]]) idom[v] = idom[idom[v]]; } }
int main() { int n, m; scanf("%d%d", &n, &m); pit = pool; fill_n(e, n, -1); fill_n(ee, n, -1); fill_n(domch, n, -1); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); *pit = {v, e[u]}; e[u] = pit++-pool; *pit = {u, ee[v]}; ee[v] = pit++-pool; } semiNca(n, 0);
for (int i = 0; i < n; i++) printf("%d: %d\n", i, idom[i]); }
|