图论：强连通分量【SCC】 (2-2)

int sz[N]; // 强连通 i 的大小

void tarjan(int u) {

low[u] = dfn[u] = ++dfncnt, s[++tp] = u, instack[u] = 1;

for (auto i:g[u]) {

const int &v = i;

if (!dfn[v]) {

tarjan(v);

low[u] = min(low[u], low[v]);

} else if (instack[v]) {

low[u] = min(low[u], dfn[v]);

}

}

if (dfn[u] == low[u]) {

++sc;

ans[sc].push_back(u);

while (s[tp] != u) {

scc[s[tp]] = sc;

sz[sc]++;

instack[s[tp]] = 0;

ans[sc].push_back(s[tp]);

--tp;

}

scc[s[tp]] = sc;

sz[sc]++;

instack[s[tp]] = 0;

--tp;

}

}

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。