Last active
November 11, 2019 04:32
-
-
Save GoBigorGoHome/2f62a3069afbc655ae96d9afad753efb to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 这种写法内存消耗大约是上一种写法的两倍,时间消耗二者差不多。 | |
template <typename Arc> | |
struct SCC { | |
int n; | |
using Graph = vector<vector<Arc>>; | |
Graph &g; | |
function<int&(Arc &)> get_v; | |
vector<int> scc_id; | |
int scc_cnt; | |
Graph scc_g; // 缩点建图 | |
SCC(int n, Graph &g, | |
function<int&(Arc &e)> get_v = [](Arc &e) { return e; }) | |
: n(n), | |
g(g), | |
get_v(move(get_v)), | |
scc_id(n + 1, -1), | |
scc_cnt(0) {} // SCCs are indexed from 0 | |
void dfs(int u) { | |
static Graph inter_scc_arcs(n + 1); | |
static vector<int> low(n + 1), order(n + 1); | |
static vector<bool> in_stack(n + 1); | |
static stack<int> s; | |
static int time; | |
order[u] = low[u] = ++time; | |
s.push(u); | |
in_stack[u] = true; | |
for (auto &e : g[u]) { | |
int& v = get_v(e); | |
if (!order[v]) { | |
dfs(v); | |
low[u] = min(low[u], low[v]); | |
} else if (in_stack[v]) { | |
low[u] = min(low[u], order[v]); | |
} | |
if (!in_stack[v]) { | |
inter_scc_arcs[u].push_back(e); | |
get_v(inter_scc_arcs[u].back()) = scc_id[v]; | |
} | |
} | |
if (order[u] == low[u]) { | |
scc_g.push_back({}); | |
while (true) { | |
int v = s.top(); | |
s.pop(); | |
in_stack[v] = false; | |
scc_id[v] = scc_cnt; | |
scc_g.back().insert(scc_g.back().end(), inter_scc_arcs[v].begin(), inter_scc_arcs[v].end()); | |
if (u == v) break; | |
} | |
++scc_cnt; | |
} | |
} | |
int find_scc() { | |
for (int i = 1; i <= n; i++) { | |
if (scc_id[i] == -1) { | |
dfs(i); | |
} | |
} | |
return scc_cnt; | |
} | |
int find_scc_from(int start) { | |
dfs(start); | |
return scc_cnt; | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template <typename Arc> | |
struct SCC { | |
int n; | |
using Graph = vector<vector<Arc>>; | |
const Graph &g; | |
function<int(const Arc &)> get_v; | |
vector<int> low, order, scc_id; | |
vector<bool> in_stack; | |
int time, scc_cnt; | |
stack<int> s; | |
SCC(int n, const Graph &g, function<int(const Arc &e)> get_v = [](const Arc &e) { return e; }) : | |
n(n), g(g), get_v(move(get_v)), low(n + 1), order(n + 1), scc_id(n + 1, -1), in_stack(n + 1), time(0), | |
scc_cnt(0) {} // SCCs are indexed from 0 | |
void dfs(int u) { | |
order[u] = low[u] = ++time; | |
s.push(u); | |
in_stack[u] = true; | |
for (auto &e : g[u]) { | |
int v = get_v(e); | |
if (!order[v]) { | |
dfs(v); | |
low[u] = min(low[u], low[v]); | |
} else if (in_stack[v]) { | |
low[u] = min(low[u], order[v]); | |
} | |
} | |
if (order[u] == low[u]) { | |
while (true) { | |
int v = s.top(); | |
s.pop(); | |
in_stack[v] = false; | |
scc_id[v] = scc_cnt; | |
if (u == v) break; | |
} | |
++scc_cnt; | |
} | |
} | |
int find_scc() { | |
for (int i = 1; i <= n; i++) { | |
if (!order[i]) { | |
dfs(i); | |
} | |
} | |
return scc_cnt; | |
} | |
int find_scc_from(int start) { | |
dfs(start); | |
return scc_cnt; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
如果是求固定起点的强连通分量,那么缩点建图可以这样写: