Template. Strongly Connect Component
使用point
來記錄點的路徑,結果存在result
。
#define maxn 1000
int id = 1;
int dfs_time = 0;
int visit[maxn] = {0};
int low[maxn];
bool in_stack[maxn] = {0};
int result[maxn]; //結果存在這裏
//result[x]代表x點所在的編號
stack<int> sta;
vector<int> point[maxn];
void scc(int now) {
visit[now] = low[now] = ++dfs_time;
sta.push(now);
in_stack[now] = 1;
for (int i : point[now]) {
if (!visit[i]) {
scc(i);
if (in_stack[i])
low[now] = min(low[now], low[i]);
}
if (visit[now] == low[now]) {
int tmp;
do {
in_stack[tmp = sta.top()] = 0;
sta.pop();
result[tmp] = id;
}while (tmp != now);
id++;
}
}