Tarjan's Strongly Connected Components

TarjanSCC.cpp

#define MAX_V 123456

struct Node {
	int id;
	int ind, lowlink;
	int SCC;
	bool visited;
};
int N, M;
Node V[MAX_V];
vector<int> E[MAX_V];

int SCC = 0;
int g_idx = 0;
deque<int> S;

void restart() {
	for (int i = 0; i < MAX_V; ++i) {
		E[i].clear();
		V[i].id = i;
		V[i].ind = 0;
		V[i].lowlink = 0;
		V[i].SCC = 0;
		V[i].visited = false;

	}
}

void dfs(int idx) {
	Node &u = V[idx];
	u.ind = g_idx;
	u.lowlink = g_idx;
	u.visited = true;

	++g_idx;
	S.push_front(idx);

	for (int i = 0; i < E[idx].size(); ++i) {
		Node &v = V[E[idx][i]];
		if (!v.visited) {
			dfs(v.id);
			u.lowlink = min(u.lowlink, v.lowlink);
		}
		else if (find(S.begin(), S.end(), v.id) != S.end()) {
			u.lowlink = min(u.lowlink, v.lowlink);
		}
	}
	if (u.lowlink == u.ind) {
		int j = -1;
		do {
			j = S.front();
			S.pop_front();
			V[j].SCC = SCC;
		} while (j != u.id);
		++SCC;
	}
}

void dfs() {
	S.clear();
	for (int i = 0; i < N; ++i) {
		if (!V[i].visited) {
			dfs(i);
		}
	}
}