Template. Strongly Connect Component

2018-08-15

使用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++;
    }
}