[C++] SCC Maker class

타잔 알고리즘으로 SCC를 만들어주는 클래스. 설명은 나중에 적어야지...

class SCCMaker {
public:
	std::vector<std::vector<int>> adj;
	std::vector<int> id; int next_id;
	std::stack<int> s;
	std::vector<bool> is_in_scc;
	std::vector<std::vector<int>> scc;
	
	SCCMaker(std::vector<std::vector<int>> &vvi) :
	id(vvi.size(), -1),
	next_id(0),
	is_in_scc(vvi.size(), false) {
		adj.swap(vvi);
		for (int i = 0; i < adj.size(); ++i) {
			if (id[i] == -1) {
				id[i] = next_id++;
				dfs(i);
			}
		}
		std::sort(scc.begin(), scc.end(), [](const std::vector<int> &l, const std::vector<int> &r) -> bool {
			return l.front() < r.front();
		});
	}
	
	int dfs(int v) {
		int min_next_id = id[v];
		s.push(v);
		for (int next : adj[v]) {
			if (id[next] == -1) {
				id[next] = next_id++;
				min_next_id = std::min(min_next_id, dfs(next));
			} else if (not is_in_scc[next]) {
				min_next_id = std::min(min_next_id, id[next]);
			}
		}
		if (min_next_id == id[v]) {
			scc.push_back(std::vector<int>());
			int w;
			do {
				w = s.top();
				is_in_scc[w] = true;
				scc.back().push_back(w + 1);
				s.pop();
			} while (w != v);
			
			std::sort(scc.back().begin(), scc.back().end());
		}
		
		return min_next_id;
	}
};