下图中有几个连通分量？

答案：

下图中有几个强连通分量？

答案：

#define MAXN 1005

int G[MAXN][MAXN]; // 邻接矩阵
int n;             // 顶点数，顶点编号从0开始

int timestamp;  // 时间戳
int dfn[MAXN];  // 第一次遍历到达u的时间戳，至少为1，为0表示u还未被访问过
int low[MAXN];  // 从顶点u开始的DFS遍历能到达的最小时间戳

stack<int> stk;
bool in_stk[MAXN]; // 记录顶点u是否在栈中

int scc_cnt;  // 记录强连通分量的个数，也用于给强连通分量编号
int id[MAXN]; // 记录顶点所属的强连通分量编号

void tarjan_dfs(int u) {
    dfn[u] = low[u] = ++timestamp; // 第一次遍历到u，初始化当前点的时间戳
    stk.push(u);
    in_stk[u] = true;
    for(int i = 0; i < n; i++) { // 遍历所有u能到的邻接点
        if(G[u][i]) {
            if(dfn[i] == 0) { // 如果这个点还没被访问过
                tarjan_dfs(i); // 遍历邻接点
                low[u] = min(low[u], low[i]); // 子结点能到的最小时间戳u能也到
            } else if(in_stk[i]) { // 如果这个点还在栈中，说明这个点比u点先访问到，它的时间戳也应该更早
                low[u] = min(low[u], dfn[i]); // 用层级更高的点的时间戳更新u的low值
            }
        }
    }
    if(dfn[u] = low[u]) { // 如果u为某个强连通分量的最高点，则可以输出这个强连通分量
        scc_cnt++; // 连通分量数加1
        int tmp;
        do {
            tmp = stk.top();
            stk.pop();
            in_stk[tmp] = false;
            id[tmp] = scc_cnt; // 标记这个点属于哪个强连通分量
        } while(tmp != u);
    }
}

void tarjan() {
    for(int i = 0; i < n; i++) { // 对所有点进行强连通分量计算
        if(dfn[i] == 0) {
            tarjan_dfs(i);
        }
    }
}

#define MAXN 1005

int G[MAXN][MAXN]; // 邻接矩阵
int n;             // 顶点数，顶点编号从0开始

int timestamp;  // 时间戳
int dfn[MAXN];  // 第一次遍历到达u的时间戳，至少为1，为0表示u还未被访问过
int low[MAXN];  // 从顶点u开始的DFS遍历能到达的最小时间戳
int fa[MAXN]; // 记录顶点的父节点

bool iscut[MAXN]; // 记录节点是否为割点
bool isbridge[MAXN][MAXN]; // 记录边是否为桥

void tarjan_cut_bridge_dfs(int x) {
    dfn[x] = low[x] = ++timestamp;
    int child = 0;
    for(int y = 0; y < n; y++) {
        if(G[x][y]) {
            if(!dfn[y]) { // y未被访问过
                child++; // x的子结点数加1
                fa[y] = x; // 记录y的父结点为x
                tarjan_cut_bridge_dfs(y);
                if(fa[x] == -1 && child >= 2) { // x是root且有>=2个子结点
                    iscut[x] = true;
                }
                if(fa[x] != -1 && low[y] >= dfn[x]) { // x不是root && x有子结点 && low[y] >= dfn[x]
                    iscut[x] = true;
                }
                if(low[y] >= dfn[x]) { // low[y] >= dfn[x]
                    isbridge[x][y] = true;
                }
                low[x] = min(low[x], low[y]);
            } else if(y != fa[x]) { // y被访问过，且不是x的父结点
                low[x] = min(low[x], low[y]);
            }
        }
    }
}

void tarjan_cut_bridge() {
    for(int i = 0; i < n; i++) { // 初始化全部的顶点的父结点为-1
        fa[i] = -1;
    }
    for(int i = 0; i < n; i++) {
        if(dfn[i] == 0) {
            tarjan_cut_bridge_dfs(i);
        }
    }
}