Skip to content

Instantly share code, notes, and snippets.

@yurahuna

yurahuna/scc.cpp Secret

Created July 17, 2016 06:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yurahuna/22706056c3c7fbca15f07f25761a5eed to your computer and use it in GitHub Desktop.
Save yurahuna/22706056c3c7fbca15f07f25761a5eed to your computer and use it in GitHub Desktop.
class SCC {
private:
const int n;
VV G;
VV rG;
V vs;
vector<bool> used;
V cmp;
public:
SCC(int _n) : n(_n), G(_n), rG(_n), used(_n), cmp(_n) {}
void addEdge(int from, int to) {
G[from].emplace_back(to);
rG[to].emplace_back(from);
}
void dfs(int v) {
used[v] = true;
for (auto&& nxt : G[v]) {
if (!used[nxt]) dfs(nxt);
}
vs.emplace_back(v);
}
void rdfs(int v, int k) {
used[v] = true;
cmp[v] = k;
for (auto&& nxt : rG[v]) {
if (!used[nxt]) rdfs(nxt, k);
}
vs.emplace_back(v);
}
int scc() {
rep(v, n) {
if (!used[v]) dfs(v);
}
used.assign(n, false);
int k = 0;
for (int i = vs.size() - 1; i >= 0; i--) {
int v = vs[i];
if (!used[v]) rdfs(v, k++);
}
return k;
}
bool same(int a, int b) {
return cmp[a] == cmp[b];
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment